<p>Given an integer, does it have a non-trivial factor? -> Non-trivially in P.</p>

<p>Given an integer, find a non-trivial factor, if there is one -> Not known to be in FP.</p>

CC BY-SA 4.0
2018-09-06T01:37:06.703Z
Or you could ask, does it have a prime factor? Then you don't need the *PRIMES is in P* paper
Bjørn Kjos-Hanssen
CC BY-SA 2.5
2010-10-01T20:31:48.320Z
2010-10-01T20:31:48.320Z
slimton
<p>Here is another example: Given a cubic graph G and a hamiltonian cycle H in G, find a different hamiltonian cycle in G. Such a cycle exists (by Smith's theorem) but, as far as I know, it is open whether it can be computed in polynomial time.</p>

CC BY-SA 2.5
2010-10-02T03:17:28.977Z
2010-10-02T03:17:28.977Z
Marek Chrobak
<p>If you give the following the same "leeway" that you do for Nash equilibria, then:</p>

<ul>
<li>Integer factorization, where the decision problem is "Is there a factorized representation of this integer?" (trivially, yes), and the search problem is to output it
</ul>

<p>A number of lattice problems could conceivably fit here with the same type of generous allowance for defining the decision problem:</p>

<ul>
<li>Shortest Vector Problem (SVP) -- decide if there's a shortest vector vs finding it
<li>Closest Vector Problem (CVP) -- decide if there's a closest vector vs finding it
</ul>

<p>Of course, these are all cases where the decision version I've mentioned isn't very interesting (because it's trivially the case). <strong>One problem that's not quite as trivial</strong>:</p>

<ul>
<li>Planar graph $k$-colorability for $k \ge 4$
</ul>

<p>The decision problem of planar graph 4-colorability is in P. But obtaining the lexicographically first such solution is NP-hard (<a href="http://portal.acm.org/citation.cfm?id=127049">Khuller/Vazirani</a>).</p>

<p>Note that the property you're really interested in is self-reducibility (or rather, non-self-reducibility). In the planar graph coloring problem, the essential issue is that the method of self-reducing the general case of $k$-colorability will destroy planarity in a graph.</p>

CC BY-SA 2.5
2010-10-01T16:11:33.583Z
2010-10-01T16:11:33.583Z
Daniel Apon
<p>Another number theory example, similar to the ones above.  It's known by <a href="http://en.wikipedia.org/wiki/Bertrand%27s_postulate">Bertrand's postulate</a> that for every positive integer $n$, there's a prime between $n$ and $2n$.  But we have no polynomial time algorithm currently to find such a prime, given $n$.  (The desired algorithm must run in polylog($n$) time.)  One can easily come up with polynomial time randomized algorithms because of the <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">prime number theorem</a>, and one can derandomize them by assuming some standard number theoretic conjectures (such as <a href="http://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture">Cramer's conjecture</a>), but no unconditionally polynomial time deterministic algorithm is known.  Related work was recently done in the <a href="http://michaelnielsen.org/polymath1/index.php?title=Finding_primes">Polymath4 project</a>; <a href="http://terrytao.wordpress.com/2010/09/21/a-deterministic-way-to-find-primes/">Tao's blog post</a> on the project is a good summary of it.</p>

CC BY-SA 3.0
2013-06-27T00:14:09.397Z
@JoeFitzsimons, I am not sure what you mean by "deterministic algorithm with expected polynomial runtime".
Chandra Chekuri
CC BY-SA 3.0
2013-06-27T19:36:10.477Z
@ChandraChekuri, "deterministic" probably is meant to say that it always gets the correct answer.
usul
CC BY-SA 3.0
2013-06-30T09:33:56.780Z
@ChandraChekuri: Sorry, my choice of wording was poor. I meant that you can find a prime number with absolute certainty in expected polynomial time, rather than simply with bounded error. At least, I think that's what I meant. It was 3 years ago.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-04T14:52:24.630Z
Even without Bertrand's postulate, you have a deterministic algorithm with expected polynomial runtime due to the Prime Number Theorem and the AKS primality test.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-02T07:05:00.703Z
2010-10-02T07:05:00.703Z
arnab
<p>At the risk of being slightly off-topic, let me give a simple and natural example of a <a href="https://cstheory.stackexchange.com/q/1521/74">theory C</a> answer: Eulerian cycles and distributed algorithms.</p>

<p>The decision problem is not <em>completely</em> trivial, in the sense that there are are both Eulerian and non-Eulerian graphs.</p>

<p>There is, however, a fast and simple distributed algorithm that solves the decision problem (in the sense that for yes-instances all nodes output "1" and for no-instances at least one node outputs "0"): each node just checks the parity of its own degree and outputs 0 or 1 accordingly.</p>

<p>But if you would like to <em>find</em> a Eulerian cycle (in the sense that each node outputs the structure of the cycle in its own neighbourhood), then we need essentially global information on the graph. It shouldn't be hard to come up with a pair of examples that shows that the problem requires $\Omega(n)$ communication rounds; on the other hand, $O(n)$ rounds is enough to solve any problem (assuming unique IDs).</p>

<p>In summary: $O(1)$-time decision problem, $\Theta(n)$-time search problem, and this is the worst possible gap.</p>

<hr>

<p><em>Edit:</em> This implicitly assumes that the graph is connected (or, equivalently, that we want to find an Eulerian cycle in each connected component).</p>

CC BY-SA 2.5
2010-10-02T22:19:25.323Z
This might be a stupid question (because I know almost nothing about distributed computing), but is there a promise that the graph is connected, or is the connectedness easy to check efficiently in a distributed way?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-02T22:43:44.397Z
Thanks, not a stupid question at all. I clarified my answer, I had forgotten to add the assumption that we deal with connected graphs here. (Usually there is little point in studying disconnected graphs from the perspective of distributed algorithms, as by definition there is no way to transmit information between the connected components, but of course this should be made explicit.)
Jukka Suomela
CC BY-SA 2.5
2010-10-04T13:51:42.307Z
Thanks!  After reading your answer, I think that it should have been obvious that the graph (= network topology) was assumed to be connected. :)
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-02T21:33:26.433Z
2010-10-02T22:38:01.020Z
2017-04-13T12:32:28.117Z
Jukka Suomela
<p>One more example; The Subset-sums equality: Given $a_1,a_2,a_3,...,,a_n$ natural numbers with  $\sum_1^n{a_i} \lt 2^n -1$. The pigeon-hole principle guarantees the existence of two subsets $I, J$ in ${1,2,..., n}$ such that $\sum_{i\in I} a_i=\sum_{j \in J} a_j$ (since the are more subsets than possible sums). The existence of polynomial time algorithm for finding sets $I$ and $J$ is a famous open problem.</p>

<p><a href="http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality">Subset-sums equality (pigeonhole version)</a>
<a href="http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality"></a></p>

CC BY-SA 2.5
2010-10-02T17:20:31.743Z
2010-10-02T17:28:10.677Z
2010-10-02T17:28:10.677Z
Mohammad Al-Turkistany
<p>Finding Tverberg partitions is of unknown complexity:</p>

<blockquote>
  <p>Theorem: Let $x_1,x_2,\dots, x_m$ be
  points in $R^d$, $m \ge (r-1)(d+1)+1$.
  Then there is a partition
  $S_1,S_2,\dots, S_r$ of
  ${1,2,\dots,m}$ such that $\cap
  _{j=1}^r \text{conv} (x_i: i \in S_j) \ne \emptyset$.</p>
</blockquote>

<p>Like with Nash equilibria, the partition is guaranteed by the theorem, but it's not known if a polytime algorithm exists to find one. </p>

<p>Gil Kalai wrote a wonderful series of posts on this topic: <a href="http://gilkalai.wordpress.com/2008/11/24/sarkarias-proof-of-tverbergs-theorem-1/">One</a>, <a href="http://gilkalai.wordpress.com/2008/11/26/sarkarias-proof-of-tverbergs-theorem-2/">Two</a> and <a href="http://gilkalai.wordpress.com/2008/12/23/seven-problems-around-tverbergs-theorem/">Three</a>.</p>

CC BY-SA 2.5
2010-10-01T18:40:40.837Z
Actually, any problem that falls into TFNP would be a good candidate I think. When an answer is guaranteed to exist by a theorem -- then, define some apparently-harder-than-P search problem over the possible solutions to accompany it.
Daniel Apon
CC BY-SA 2.5
2010-10-01T17:07:53.747Z
2010-10-01T17:07:53.747Z
Suresh Venkat
<ul>
<li>Decision version is (highly) non-trival in <strong>P</strong>: $k$-colourability ($k$ fixed) on graphs without induced path with five vertices; 
due to this <a href="http://link.springer.com/article/10.1007%2Fs00453-008-9197-8">paper</a>.</li>
<li>Search version is <strong>NP</strong>-hard: Finding the chromatic number of graphs without induced path with five vertices; 
due to this <a href="http://link.springer.com/chapter/10.1007/3-540-45477-2_23">paper</a>.</li>
</ul>

CC BY-SA 3.0
2013-06-26T19:50:17.120Z
You perhaps meant to say that _for fixed $k$_, the decision version is in P.
András Salamon
CC BY-SA 3.0
2013-06-26T15:29:29.290Z
2013-06-27T11:39:44.397Z
2013-06-27T11:39:44.397Z
Peng O
<p>In all the examples above the decision problem is in P and the search problem is not known to be in P but not known to be NP-hard either. I want to point out that it is possible to have an NP-hard search problem whose decision version is easy. </p>

<p>Consider the generalized satisfiability problem for given relations $R_1,\ldots,R_k$ over Boolean domain $\{0,1\}$. An instance is an expression of the form 
$$
R_{i_1}(t_{11},\ldots,t_{1r_1}) \wedge \cdots \wedge R_{i_m}(t_{m1},\ldots,t_{mr_m})
$$
where the $t_{ij}$'s are either variables or constants in ${0,1}$, and $r_1,\ldots,r_m$ are the arities of $R_1,\ldots,R_k$ (this is the same framework as in Schaeffer's dichotomy theorem with constants, in case you know what it is). The search problem is: given such an expression, find a lexicographically minimal solution, if there is one.</p>

<p>It was shown by Reith and Vollmer <a href="http://portal.acm.org/citation.cfm?id=952837">here</a> that there exists a choice of relations $R_1,\ldots,R_k$ that make this problem NP-hard (actually OptP-complete) but keep the satisfiability problem easy (quite trivial actually). An example given in the paper is $R = \{(1,0,0),(0,1,0),(1,1,1)\}$ (here $k = 1$). Once the satisfiability problem is solvable in polynomial-time, the question whether there exists a lexicographically minimal satisfying assignment is trivial.</p>

<p>See Corollary 13 and the example following it in the paper above (at least in <a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=7&amp;ved=0CDUQFjAG&amp;url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.45.6990%26rep%3Drep1%26type%3Dpdf&amp;rct=j&amp;q=Vollmer%20lexicographically%20minimal&amp;ei=TM-pTPrjNJPT4waY3KjIDQ&amp;usg=AFQjCNEoL6-wM42SNoUWvg0cGamtOpmOOQ&amp;sig2=XWsFZU6HnQZIa6I3akQv0Q&amp;cad=rja">this</a> on-line version). </p>

CC BY-SA 2.5
2010-10-04T13:14:01.267Z
2010-10-04T13:14:01.267Z
slimton
<p>Take a "pairing-friendly" elliptic curve. That is, a curve that has a one bilinear map $e$ associated with it - with $e (a + b, c + d) = e (a c) e (a d) e (b c) e (b d)$ such that $e$ is difficult to invert).</p>

<p>Such pairings are used widely in cryptography, partially since given $e$, it is trivial to solve Decisional Diffie-Hellman (given $(g, h, g^a, h^b)$, decide if $a = b$: just verify whether $e (g, h^b) = e (h, g^a)$). However, it is still conjectured that the search/computational Diffie-Hellman problem is difficult.</p>

<p>Such groups are also generalized to "gap groups".</p>

CC BY-SA 3.0
2013-06-26T18:09:01.050Z
2013-06-26T18:09:01.050Z
cryptocat
<p>Let's notch up the complexity a bit.</p>

<p>Many decision problems about vector addition systems (VAS) are EXPSPACE-complete, but may require much larger witnesses.  For instance, deciding whether the language of a VAS is regular is EXPSPACE-complete (e.g. <a href="http://dx.doi.org/10.1007/978-3-642-22993-0_13" rel="nofollow">Blockelet &amp; Schmitz, 2011</a>), but the smallest equivalent finite-state automaton might be of Ackermannian size (<a href="http://dx.doi.org/10.1016/0022-0000(81)90067-2" rel="nofollow">Valk &amp; Vidal-Naquet, 1981</a>).  The explanation behind this huge gap is that there exist much smaller witnesses of <em>non</em>-regularity.</p>

CC BY-SA 3.0
2013-10-29T15:01:04.350Z
2013-10-29T15:01:04.350Z
Sylvain
<p>I guess Planar Perfect Matching got missed out from this list.</p>

<ul>
<li>The decision version is in NC (even the counting version is in $\mathsf{NC}$) by a parallel version (see <a href="http://www.imsc.res.in/~meena/papers/pfaffians.ps.gz" rel="nofollow">Mahajan-Subramanya-Vinay</a>) of Kastelyn's algorithm</li>
<li>The search version remains unparallelised to date i.e there is no known deterministic $\mathsf{NC}$ algorithm for this problem (though if we drop either of the parallel or deterministic restrictions there are well known algorithms - <a href="http://en.wikipedia.org/wiki/Blossom_algorithm" rel="nofollow">Edmonds</a> and <a href="http://www.eecs.berkeley.edu/~vazirani/pubs/matching.pdf" rel="nofollow">Mulmuley-Vazirani-Vazirani</a>/<a href="http://www.columbia.edu/~cs2035/courses/ieor8100.F12/KUW86.pdf" rel="nofollow">Karp-Upfal-Wigderson</a>, respectively.</li>
</ul>

CC BY-SA 3.0
2013-10-28T19:33:44.187Z
2013-10-28T19:33:44.187Z
SamiD
<p>Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete).</p>

<p>What are some other examples of problems where the decision version is easy but the search version is relatively difficult (compared the the decision version)? </p>

<p>I would be particularly interested in problems where the decision version is non-trival (unlike the case with Nash equilibrium).</p>

CC BY-SA 2.5
2010-10-01T14:04:01.423Z
Should probably be community wiki: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/239#239
Dave Clarke
CC BY-SA 2.5
2010-10-01T14:09:14.757Z
@supercooldave: I wouldn't hurry with CW in this case. It may turn out that there are very few *natural* problems with a non-trivial but easy decision version and hard search version. This is not necessarily a "big-list".
Jukka Suomela
CC BY-SA 2.5
2010-10-01T14:16:50.117Z
I went with the heuristic that big list = community wiki.
Dave Clarke
CC BY-SA 2.5
2010-10-01T14:56:07.190Z
So this raises the question "what is the natural decision problem to be associated with a search problem?". I think existence of NE is not the natural decision problem associate with NE.
Kaveh
CC BY-SA 2.5
2010-10-01T15:56:42.403Z
@Kaveh: You can define that decision problem for Nash (if you specify an encoding of a solution to Nash), but the problem is whether it is the same complexity as Nash or not, or formally, whether that decision problem is reducible to Nash.  I doubt it because finding a Nash equilibrium satisfying some additional constraint is often NP-hard.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-02T04:03:14.870Z
Interesting that we don't yet have an example where the decision problem is nontrivial...
arnab
CC BY-SA 2.5
2010-10-02T09:21:04.437Z
@arnab: We do have, the answer by slimton for example.
Jukka Suomela
CC BY-SA 2.5
2010-10-02T13:19:12.640Z
@Jukka: Oops, I meant to say, other than finding nontrivial factor.
arnab
<cc.complexity-theory><big-list>
Easy decision problem, hard search problem
Travis Service
# Easy decision problem, hard search problem

(Asked by: username_0 on 2010-10-01)

Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete).

What are some other examples of problems where the decision version is easy but the search version is relatively difficult (compared the the decision version)?

I would be particularly interested in problems where the decision version is non-trival (unlike the case with Nash equilibrium).

**Tags:** cc.complexity-theory, big-list
> **Comments:**
> **username_1**: Should probably be community wiki: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/239#239  
> **username_2**: @supercooldave: I wouldn't hurry with CW in this case. It may turn out that there are very few *natural* problems with a non-trivial but easy decision version and hard search version. This is not necessarily a "big-list".  
> **username_1**: I went with the heuristic that big list = community wiki.  
> **username_3**: So this raises the question "what is the natural decision problem to be associated with a search problem?". I think existence of NE is not the natural decision problem associate with NE.  
> **username_4**: @Kaveh: You can define that decision problem for Nash (if you specify an encoding of a solution to Nash), but the problem is whether it is the same complexity as Nash or not, or formally, whether that decision problem is reducible to Nash.  I doubt it because finding a Nash equilibrium satisfying some additional constraint is often NP-hard.  
> **username_5**: Interesting that we don't yet have an example where the decision problem is nontrivial...  
> **username_2**: @arnab: We do have, the answer by slimton for example.  
> **username_5**: @Jukka: Oops, I meant to say, other than finding nontrivial factor.  

---

## 12 answers

### Answer by username_6 on 2010-10-01. Score: 41

Given an integer, does it have a non-trivial factor? -> Non-trivially in P.

Given an integer, find a non-trivial factor, if there is one -> Not known to be in FP.

> **Comments:**
> **username_7**: Or you could ask, does it have a prime factor? Then you don't need the *PRIMES is in P* paper  

---

### Answer by username_8 on 2010-10-02. Score: 30

Here is another example: Given a cubic graph G and a hamiltonian cycle H in G, find a different hamiltonian cycle in G. Such a cycle exists (by Smith's theorem) but, as far as I know, it is open whether it can be computed in polynomial time.


---

### Answer by username_9 on 2010-10-01. Score: 21

If you give the following the same "leeway" that you do for Nash equilibria, then:

* Integer factorization, where the decision problem is "Is there a factorized representation of this integer?" (trivially, yes), and the search problem is to output it

A number of lattice problems could conceivably fit here with the same type of generous allowance for defining the decision problem:

* Shortest Vector Problem (SVP) -- decide if there's a shortest vector vs finding it* Closest Vector Problem (CVP) -- decide if there's a closest vector vs finding it

Of course, these are all cases where the decision version I've mentioned isn't very interesting (because it's trivially the case). **One problem that's not quite as trivial**:

* Planar graph $k$-colorability for $k \ge 4$

The decision problem of planar graph 4-colorability is in P. But obtaining the lexicographically first such solution is NP-hard ([Khuller/Vazirani](http://portal.acm.org/citation.cfm?id=127049)).

Note that the property you're really interested in is self-reducibility (or rather, non-self-reducibility). In the planar graph coloring problem, the essential issue is that the method of self-reducing the general case of $k$-colorability will destroy planarity in a graph.


---

### Answer by username_13 on 2010-10-02. Score: 15

One more example; The Subset-sums equality: Given $a\_1,a\_2,a\_3,...,,a\_n$ natural numbers with $\sum\_1^n{a\_i} \lt 2^n -1$. The pigeon-hole principle guarantees the existence of two subsets $I, J$ in ${1,2,..., n}$ such that $\sum\_{i\in I} a\_i=\sum\_{j \in J} a\_j$ (since the are more subsets than possible sums). The existence of polynomial time algorithm for finding sets $I$ and $J$ is a famous open problem.

[Subset-sums equality (pigeonhole version)](http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality)


---

### Answer by username_5 on 2010-10-02. Score: 13

Another number theory example, similar to the ones above. It's known by [Bertrand's postulate](http://en.wikipedia.org/wiki/Bertrand%27s_postulate) that for every positive integer $n$, there's a prime between $n$ and $2n$. But we have no polynomial time algorithm currently to find such a prime, given $n$. (The desired algorithm must run in polylog($n$) time.) One can easily come up with polynomial time randomized algorithms because of the [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem), and one can derandomize them by assuming some standard number theoretic conjectures (such as [Cramer's conjecture](http://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture)), but no unconditionally polynomial time deterministic algorithm is known. Related work was recently done in the [Polymath4 project](http://michaelnielsen.org/polymath1/index.php?title=Finding_primes); [Tao's blog post](http://terrytao.wordpress.com/2010/09/21/a-deterministic-way-to-find-primes/) on the project is a good summary of it.

> **Comments:**
> **username_12**: Even without Bertrand's postulate, you have a deterministic algorithm with expected polynomial runtime due to the Prime Number Theorem and the AKS primality test.  
> **username_10**: @JoeFitzsimons, I am not sure what you mean by "deterministic algorithm with expected polynomial runtime".  
> **username_11**: @ChandraChekuri, "deterministic" probably is meant to say that it always gets the correct answer.  
> **username_12**: @ChandraChekuri: Sorry, my choice of wording was poor. I meant that you can find a prime number with absolute certainty in expected polynomial time, rather than simply with bounded error. At least, I think that's what I meant. It was 3 years ago.  

---

### Answer by username_2 on 2010-10-02. Score: 12

At the risk of being slightly off-topic, let me give a simple and natural example of a [theory C](https://cstheory.stackexchange.com/q/1521/74) answer: Eulerian cycles and distributed algorithms.

The decision problem is not *completely* trivial, in the sense that there are are both Eulerian and non-Eulerian graphs.

There is, however, a fast and simple distributed algorithm that solves the decision problem (in the sense that for yes-instances all nodes output "1" and for no-instances at least one node outputs "0"): each node just checks the parity of its own degree and outputs 0 or 1 accordingly.

But if you would like to *find* a Eulerian cycle (in the sense that each node outputs the structure of the cycle in its own neighbourhood), then we need essentially global information on the graph. It shouldn't be hard to come up with a pair of examples that shows that the problem requires $\Omega(n)$ communication rounds; on the other hand, $O(n)$ rounds is enough to solve any problem (assuming unique IDs).

In summary: $O(1)$-time decision problem, $\Theta(n)$-time search problem, and this is the worst possible gap.

---

*Edit:* This implicitly assumes that the graph is connected (or, equivalently, that we want to find an Eulerian cycle in each connected component).

> **Comments:**
> **username_4**: This might be a stupid question (because I know almost nothing about distributed computing), but is there a promise that the graph is connected, or is the connectedness easy to check efficiently in a distributed way?  
> **username_2**: Thanks, not a stupid question at all. I clarified my answer, I had forgotten to add the assumption that we deal with connected graphs here. (Usually there is little point in studying disconnected graphs from the perspective of distributed algorithms, as by definition there is no way to transmit information between the connected components, but of course this should be made explicit.)  
> **username_4**: Thanks!  After reading your answer, I think that it should have been obvious that the graph (= network topology) was assumed to be connected. :)  

---

### Answer by username_14 on 2010-10-01. Score: 10

Finding Tverberg partitions is of unknown complexity:

> Theorem: Let $x\_1,x\_2,\dots, x\_m$ be
> points in $R^d$, $m \ge (r-1)(d+1)+1$.
> Then there is a partition
> $S\_1,S\_2,\dots, S\_r$ of
> ${1,2,\dots,m}$ such that $\cap
> \_{j=1}^r \text{conv} (x\_i: i \in S\_j) \ne \emptyset$.

Like with Nash equilibria, the partition is guaranteed by the theorem, but it's not known if a polytime algorithm exists to find one.

Gil Kalai wrote a wonderful series of posts on this topic: [One](http://gilkalai.wordpress.com/2008/11/24/sarkarias-proof-of-tverbergs-theorem-1/), [Two](http://gilkalai.wordpress.com/2008/11/26/sarkarias-proof-of-tverbergs-theorem-2/) and [Three](http://gilkalai.wordpress.com/2008/12/23/seven-problems-around-tverbergs-theorem/).

> **Comments:**
> **username_9**: Actually, any problem that falls into TFNP would be a good candidate I think. When an answer is guaranteed to exist by a theorem -- then, define some apparently-harder-than-P search problem over the possible solutions to accompany it.  

---

### Answer by username_6 on 2010-10-04. Score: 7

In all the examples above the decision problem is in P and the search problem is not known to be in P but not known to be NP-hard either. I want to point out that it is possible to have an NP-hard search problem whose decision version is easy.

Consider the generalized satisfiability problem for given relations $R\_1,\ldots,R\_k$ over Boolean domain $\{0,1\}$. An instance is an expression of the form
$$
R\_{i\_1}(t\_{11},\ldots,t\_{1r\_1}) \wedge \cdots \wedge R\_{i\_m}(t\_{m1},\ldots,t\_{mr\_m})
$$
where the $t\_{ij}$'s are either variables or constants in ${0,1}$, and $r\_1,\ldots,r\_m$ are the arities of $R\_1,\ldots,R\_k$ (this is the same framework as in Schaeffer's dichotomy theorem with constants, in case you know what it is). The search problem is: given such an expression, find a lexicographically minimal solution, if there is one.

It was shown by Reith and Vollmer [here](http://portal.acm.org/citation.cfm?id=952837) that there exists a choice of relations $R\_1,\ldots,R\_k$ that make this problem NP-hard (actually OptP-complete) but keep the satisfiability problem easy (quite trivial actually). An example given in the paper is $R = \{(1,0,0),(0,1,0),(1,1,1)\}$ (here $k = 1$). Once the satisfiability problem is solvable in polynomial-time, the question whether there exists a lexicographically minimal satisfying assignment is trivial.

See Corollary 13 and the example following it in the paper above (at least in [this](http://www.google.com/url?sa=t&source=web&cd=7&ved=0CDUQFjAG&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.45.6990%26rep%3Drep1%26type%3Dpdf&rct=j&q=Vollmer%20lexicographically%20minimal&ei=TM-pTPrjNJPT4waY3KjIDQ&usg=AFQjCNEoL6-wM42SNoUWvg0cGamtOpmOOQ&sig2=XWsFZU6HnQZIa6I3akQv0Q&cad=rja) on-line version).


---

### Answer by username_15 on 2013-06-26. Score: 6

* Decision version is (highly) non-trival in **P**: $k$-colourability ($k$ fixed) on graphs without induced path with five vertices;
  due to this [paper](http://link.springer.com/article/10.1007%2Fs00453-008-9197-8).
* Search version is **NP**-hard: Finding the chromatic number of graphs without induced path with five vertices;
  due to this [paper](http://link.springer.com/chapter/10.1007/3-540-45477-2_23).

> **Comments:**
> **username_16**: You perhaps meant to say that _for fixed $k$_, the decision version is in P.  

---

### Answer by username_17 on 2013-06-26. Score: 4

Take a "pairing-friendly" elliptic curve. That is, a curve that has a one bilinear map $e$ associated with it - with $e (a + b, c + d) = e (a c) e (a d) e (b c) e (b d)$ such that $e$ is difficult to invert).

Such pairings are used widely in cryptography, partially since given $e$, it is trivial to solve Decisional Diffie-Hellman (given $(g, h, g^a, h^b)$, decide if $a = b$: just verify whether $e (g, h^b) = e (h, g^a)$). However, it is still conjectured that the search/computational Diffie-Hellman problem is difficult.

Such groups are also generalized to "gap groups".


---

### Answer by username_18 on 2013-10-29. Score: 2

Let's notch up the complexity a bit.

Many decision problems about vector addition systems (VAS) are EXPSPACE-complete, but may require much larger witnesses. For instance, deciding whether the language of a VAS is regular is EXPSPACE-complete (e.g. [Blockelet & Schmitz, 2011](http://dx.doi.org/10.1007/978-3-642-22993-0_13)), but the smallest equivalent finite-state automaton might be of Ackermannian size ([Valk & Vidal-Naquet, 1981](http://dx.doi.org/10.1016/0022-0000(81)90067-2)). The explanation behind this huge gap is that there exist much smaller witnesses of *non*-regularity.


---

### Answer by username_19 on 2013-10-28. Score: 2

I guess Planar Perfect Matching got missed out from this list.

* The decision version is in NC (even the counting version is in $\mathsf{NC}$) by a parallel version (see [Mahajan-Subramanya-Vinay](http://www.imsc.res.in/~meena/papers/pfaffians.ps.gz)) of Kastelyn's algorithm
* The search version remains unparallelised to date i.e there is no known deterministic $\mathsf{NC}$ algorithm for this problem (though if we drop either of the parallel or deterministic restrictions there are well known algorithms - [Edmonds](http://en.wikipedia.org/wiki/Blossom_algorithm) and [Mulmuley-Vazirani-Vazirani](http://www.eecs.berkeley.edu/~vazirani/pubs/matching.pdf)/[Karp-Upfal-Wigderson](http://www.columbia.edu/~cs2035/courses/ieor8100.F12/KUW86.pdf), respectively.


---

