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

Question

One such problem I know is integer factorization.

What are other interesting cases?

Answer 1

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 2

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 3

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

Answer 4

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 5

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$_{\sqrt{n}}$ and GapSVP$_{\sqrt{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 6

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 7

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)

Answer 8

Since you mentioned integer factoring, an analogous problem is the discrete log problem.

Given the cyclic group $G = \mathbb{Z}^*_p$ for a prime $p$ and any generator $g$ of $G$ along with another $h \in G$ (which will also be a generator), the discrete log asks to find $x \in \mathbb{Z}_{p-1}$ such that $g^x = h$. To convert to decision problem, let $k$ be any positive integer $< \log_2(p-1)$. The problem is then: Is the $k^{th}$ bit of $x$ true? This is also in NP $\cap$ coNP but not known to be in P.

Answer 9

This was mentioned in a comment on this answer, but I think it's important enough to warrant its own answer, especially since new results have arisen since then.

A parity game is defined by a directed graph where each vertex is labeled by an integer called the priority, and a distinguished start vertex. There is a token which is initially on the start vertex. Players take turns to move the token from the current vertex $u$ to a vertex $v$ along an edge $u → v$. After $ω$ steps, the winner is determined by the parity of the highest priority of a vertex visited infinitely often.

Parity games are determined (because they are Borel; actually, they are even positionally determined, meaning that there always exists a winning strategy for one of the players which only depends on the current vertex and not on the whole history of the play). The problem is to determine which player has a winning strategy.

For a long time, this problem was only known to lie in NP ∩ co-NP. It was a breakthrough when it was shown in 2017 that it can be solved in quasipolynomial time (Calude, Jain, Khoussainov, Li & Stephan, Deciding Parity Games in Quasipolynomial Time). The problem is not known to be in P and is, I think, largely considered as a good candidate for being NP-intermediate.

Answer 10

Suppose that $M$ is a triangulated three-manifold. Then deciding if $M$ is homeomorphic to the three-sphere lies in NP and also in co-NP. Its containment in NP is due to Schleimer (see also Ivanov). The containment in co-NP relies on GRH and is due to Zentner.