Problems known to be in both NP and coNP, but not known to be in P - MathOverflow

Problems known to be in both NP and coNP, but not known to be in P

2010-07-14T10:03:22Z

One such problem I know is integer factorization.

What are other interesting cases?

Answer by lhf for Problems known to be in both NP and coNP, but not known to be in P

2010-07-14T10:48:50Z

There's a short list in http://kintali.wordpress.com/2010/06/06/np-intersect-conp/

Answer by Sam Nead for Problems known to be in both NP and coNP, but not known to be in P

2010-07-14T10:49:53Z

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.

Answer by Niel de Beaudrap for Problems known to be in both NP and coNP, but not known to be in P

2010-07-14T14:03:11Z

A lattice L is the image of ℤⁿ ⊂ ℝⁿ under the action of a matrix A ∈ GL(ℝⁿ). The rank of L is the dimension n of the space it lives in.

The closest vector problem (CVP) asks, for a vector x ∈ ℝⁿ, whether the closest element of L is "close" to x (distance at most 1 in the Euclidean norm) or not.
The shortest vector problem (SVP) asks whether the shortest non-zero element of L is "short" (has length at most 1) or not.

Both problems are NP-complete. There is an active research programme on finding efficiently solvable approximation versions, which may be interpreted as problems where you are promised that there is an approximation-factor gap f(n) between YES instances and NO instances. This introduces the promise problem-families

GapCVP_f(n)
--- asks whether the closest vector in L to x is "close" (distance at most 1 away) or "far" (distance at least f(n) away), given that at least one of these is true;
GapSVP_f(n)
--- asks whether the shortest non-zero vector in L is "short" (length at most 1) or "long" (length at least f(n)), given that at least one of these is true.

The paper "Lattice problems in NP ∩ coNP" shows that the approximation problems GapCVP_√n and GapSVP_√n are both in (as you might guess) NP ∩ 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.

Answer by Peter Shor for Problems known to be in both NP and coNP, but not known to be in P

2010-07-17T19:51:56Z

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.

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.

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}$?

Answer by Scott Aaronson for Problems known to be in both NP and coNP, but not known to be in P

2010-07-17T20:35:40Z

Under popular derandomization assumptions, the following problems are in $NP\cap coNP$:

Graph Isomorphism and Automorphism (as well as Group Isomorphism, Ring Isomorphism, ...)
Group Membership (e.g., given invertible matrices $A$ and $B_1,...,B_k$, is $A$ in the group generated by $B_1,...,B_k$?)

(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 this paper by Klivans and van Melkebeek.)

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

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 don't have a promise (or where the promise is easy to check).

Answer by Marcos Villagra for Problems known to be in both NP and coNP, but not known to be in P

2010-07-21T07:39:11Z

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 paper. In fact, this problem is in TFNP (defined by Meggido and Papadimitriou). Still no polynomial-time algorithms exists for this class of problems.

Answer by Gil Kalai for Problems known to be in both NP and coNP, but not known to be in P

2011-07-14T20:00:26Z

A AUSO (acyclic unique sink orientation) is an acyclic orientation of the discrete n-dimensional cube so that every face has a unique sink.

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.

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.

A more general question is to replace the discrete cube by an abstract LP problem defuned by Sharir and Welzl.

Problems: 1) Is the problem for discrete cubes computationally equivalent to the problem for abstract LP problems?

2) Is the decision problem in P?

3) Perhaps this decision problem (or the more general one for abstract LP) complete for the class $NP \cap coNP$?

Maybe this problem is complete for NP intersection coNP?

(On the other hand it may well be in P)