Problems known to be in both NP and coNP, but not known to be in P - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T22:47:41Z http://mathoverflow.net/feeds/question/31821 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p Problems known to be in both NP and coNP, but not known to be in P falagar 2010-07-14T10:03:22Z 2011-07-14T20:00:26Z <p>One such problem I know is integer factorization.</p> <p>What are other interesting cases?</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/31830#31830 Answer by lhf for Problems known to be in both NP and coNP, but not known to be in P lhf 2010-07-14T10:48:50Z 2010-07-14T10:48:50Z <p>There's a short list in <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/" rel="nofollow">http://kintali.wordpress.com/2010/06/06/np-intersect-conp/</a></p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/31831#31831 Answer by Sam Nead for Problems known to be in both NP and coNP, but not known to be in P Sam Nead 2010-07-14T10:49:53Z 2010-07-14T18:19:22Z <p>Suppose that $K$ is a knot in the three-sphere. Then deciding if $K$ is the unknot lies in NP and also in co-NP. Its containment in NP is due to Hass, Lagarias, and Pippenger and the containment in co-NP has been shown (but not yet written up?) by Agol.</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/31859#31859 Answer by Niel de Beaudrap for Problems known to be in both NP and coNP, but not known to be in P Niel de Beaudrap 2010-07-14T14:03:11Z 2010-07-14T15:10:13Z <p>A <em>lattice L</em> is the image of ℤ<sup><em>n</em></sup>&nbsp;&sub;&nbsp;&#8477;<sup><em>n</em></sup> under the action of a matrix <em>A</em>&nbsp;&isin;&nbsp;GL(&#8477;<sup><em>n</em></sup>). The rank of <em>L</em> is the dimension <em>n</em> of the space it lives in.</p> <ul> <li>The <em>closest vector problem</em> (CVP) asks, for a vector <strong>x</strong>&nbsp;&isin;&nbsp;&#8477;<sup><em>n</em></sup>, whether the closest element of <em>L</em> is "close" to <strong>x</strong> (distance at most 1 in the Euclidean norm) or not.</li> <li>The <em>shortest vector problem</em> (SVP) asks whether the shortest non-zero element of <em>L</em> is "short" (has length at most 1) or not.</li> </ul> <p>Both problems are NP-complete. There is an active research programme on finding efficiently solvable <em>approximation</em> versions, which may be interpreted as problems where you are promised that there is an approximation-factor gap <em>f(n)</em> between YES instances and NO instances. This introduces the promise problem-families</p> <ul> <li><p>GapCVP<sub><em>f(n)</em>&nbsp;</sub><br> --- asks whether the closest vector in <em>L</em> to <strong>x</strong> is "close" (distance at most 1 away) or "far" (distance at least <em>f(n)</em> away), given that at least one of these is true;</p></li> <li><p>GapSVP<sub><em>f(n)</em>&nbsp;</sub><br> --- asks whether the shortest non-zero vector in <em>L</em> is "short" (length at most 1) or "long" (length at least <em>f(n)</em>), given that at least one of these is true.</p></li> </ul> <p>The paper "<a href="http://www.cs.tau.ac.il/~odedr/goto.php?name=cvpconp_pdf&amp;link=http://www.cs.tau.ac.il/~odedr/papers/cvpconp.pdf" rel="nofollow">Lattice problems in NP &cap; coNP</a>" shows that the approximation problems GapCVP<sub>&radic;<em>n</em></sub> and GapSVP<sub>&radic;<em>n</em></sub> are both in (as you might guess) NP&nbsp;&cap;&nbsp;coNP; furthermore, the witnesses for both YES and NO instances can in principle be generated from a particular probability distribution, and so are in some sense plentiful for this approximation factor.</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/32309#32309 Answer by Peter Shor for Problems known to be in both NP and coNP, but not known to be in P Peter Shor 2010-07-17T19:51:56Z 2010-07-17T19:51:56Z <p>One of my favorite problems in NP $\cap$ co-NP is deciding who wins a simple stochastic game. The game is played on a directed graph by two players, call them A and B. This graph contains several types of nodes. There is a source node and two sink nodes, one for each of the players. There are also random nodes (which include the source), "A" nodes, and "B" nodes. At the start of the game, for each "A" or "B" node, the corresponding player chooses one of the edges leading away from it, without seeing the other player's choices. </p> <p>A token is then placed on the start node. The token undergoes a random walk. When it hits a random node, it chooses randomly among the edges directed away from this node. When it hits an "A" or "B" node, the token takes the chosen edge.</p> <p>Each player's goal is to maximize the probability that the token lands on their sink node. The question in NP $\cap$ co-NP is: does player A have a winning strategy that ensures the token lands on his sink node with probability at least $\frac{1}{2}$?</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/32312#32312 Answer by Scott Aaronson for Problems known to be in both NP and coNP, but not known to be in P Scott Aaronson 2010-07-17T20:35:40Z 2010-07-17T20:35:40Z <p>Under popular derandomization assumptions, the following problems are in $NP\cap coNP$:</p> <ul> <li>Graph Isomorphism and Automorphism (as well as Group Isomorphism, Ring Isomorphism, ...)</li> <li>Group Membership (e.g., given invertible matrices $A$ and $B_1,...,B_k$, is $A$ in the group generated by $B_1,...,B_k$?)</li> </ul> <p>(More precisely, these problems are known to be in $NP\cap coAM$. $coAM$ is a "close cousin" of $coNP$, and equals the latter under derandomization hypotheses: see <a href="http://www.cs.wisc.edu/~dieter/Research/r-gni.html" rel="nofollow">this paper</a> by Klivans and van Melkebeek.)</p> <p>Besides factoring, there are various other number-theoretic problems in $NP\cap coNP$, such as decision versions of Discrete Logarithm (both in $Z_p^*$ and in elliptic curve groups).</p> <p>If you're willing to allow promise problems (i.e., the algorithm only has to output a correct answer if the input satisfies some property), then there are lots of natural examples of $NP\cap coNP$ problems. A trivial example is, "given two Boolean formulas F and G, and promised that exactly one of them is satisfiable, decide which." A nontrivial example is the Approximate Shortest Vector problem, mentioned previously by Niel. What's rarer are interesting $NP\cap coNP$ problems that <i>don't</i> have a promise (or where the promise is easy to check).</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/32758#32758 Answer by Marcos Villagra for Problems known to be in both NP and coNP, but not known to be in P Marcos Villagra 2010-07-21T07:39:11Z 2010-07-21T07:39:11Z <p>A different nice example is a variant of the subset sum problem called Pigeonhole Subset Sum. Given $n$ positive integers with sum less than $2^n-1$, find two disjoint nonempty subsets whose sums are equal. See this <a href="http://portal.acm.org/citation.cfm?id=639541" rel="nofollow">paper</a>. In fact, this problem is in TFNP (defined by <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V1G-45GMT3B-2K&amp;_user=3304344&amp;_coverDate=04/30/1991&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1406950278&amp;_rerunOrigin=google&amp;_acct=C000050802&amp;_version=1&amp;_urlVersion=0&amp;_userid=3304344&amp;md5=4c25392989c40cd15e22655cff593dc3" rel="nofollow">Meggido and Papadimitriou</a>). Still no polynomial-time algorithms exists for this class of problems.</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/70367#70367 Answer by Gil Kalai for Problems known to be in both NP and coNP, but not known to be in P Gil Kalai 2011-07-14T20:00:26Z 2011-07-14T20:00:26Z <p>A AUSO (acyclic unique sink orientation) is an acyclic orientation of the discrete n-dimensional cube so that every face has a unique sink. </p> <p>The following decision problem is in NP and also in coNP. Given an AUSO and a face F is the unique sink of F the same as the unique sink of the entire cube. It is in $NP\cap coNP$ because when you are given a vertex it is easy to check, is it in F; is it the unique sink of F; is it the unique sink of the entire cube.</p> <p>The search problem of finding the unique sink is more well known and has various applications. It is easily seen to be equivalent to the decision problem we mentioned.</p> <p>A more general question is to replace the discrete cube by an abstract LP problem defuned by Sharir and Welzl.</p> <p>Problems: 1) Is the problem for discrete cubes computationally equivalent to the problem for abstract LP problems?</p> <p>2) Is the decision problem in P? </p> <p>3) Perhaps this decision problem (or the more general one for abstract LP) complete for the class $NP \cap coNP$?</p> <p>Maybe this problem is complete for NP intersection coNP?</p> <p>(On the other hand it may well be in P)</p>