Easy decision problem, hard search problem

Question

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).

Answer 1

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.

Answer 2

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).

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 3

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 4

Let $G=G(n,1/2)$, the random graph on $1,\ldots,n$, in which each edge is independently present with probability $1/2$. Choose $n^{1/3}$ vertices of $G$ uniformly at random and add all edges between them; call the resulting graph $H$. Then $H$ has a clique of size $n^{1/3}$.

Search problem: find a clique of size at least $10\log n$.

Answer 5

Another number theory example, similar to the ones above. It's known by Bertrand's 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, and one can derandomize them by assuming some standard number theoretic conjectures (such as Cramer's conjecture), but no unconditionally polynomial time deterministic algorithm is known. Related work was recently done in the Polymath4 project; Tao's blog post on the project is a good summary of it.

Answer 6

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, Two and Three.

Answer 7

At the risk of being slightly off-topic, let me give a simple and natural example of a theory C 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).

Answer 8

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)

Answer 9

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 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 on-line version).