Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

One such problem I know is integer factorization.

What are other interesting cases?

share|improve this question
    
So, presumably you are taking a definition of NP that includes things that are not decision problems? Or can you formulate integer factorization as a decision problem? –  Emil Jul 14 '10 at 11:14
3  
Integer factorization can be converted into decision problem: given $n$ and $k$ return YES if $k$-th bit of the smallest prime divisor of $n$ is equal to $1$. –  falagar Jul 14 '10 at 11:30
    
Do other problems thought to be NP-Intermediate (en.wikipedia.org/wiki/NP-Intermediate) satisfy this? –  BlueRaja Jul 14 '10 at 15:35
    
@BlueRaja: It's not clear exactly what you're asking. For any function problem in NP, you can turn it into a decision problem in NP. One interesting question would be: for any function problem in NP-intermediate, can you turn it into a decision problem in NP-intermediate (or do some NP-intermediate function problems automatically turn into NP-complete decision problems)? I don't have any idea how to answer this question. –  Peter Shor Jul 28 '10 at 21:14

7 Answers 7

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

share|improve this answer
    
Here's a recent reference on simple stochastic games and related problems: springerlink.com/content/5500m01711124283. –  Peter Shor Jul 18 '10 at 13:06
    
Presumably A and B are disjoint? –  András Salamon Jul 19 '10 at 7:25
1  
Yes, the vertex set of the graph is the disjoint union of random nodes, "A" nodes, "B" nodes, and the two sinks. –  Peter Shor Jul 19 '10 at 20:20
    
Deciding the winner in parity games is also in $NP\cap co-NP$ but not known to be in $P$, and parity games are simpler (in my opinion) than stochastic games. –  Denis Jun 9 '13 at 23:04

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

share|improve this answer
    
I thought whether GI is in coNP is an open problem? –  Turbo Dec 27 '11 at 7:01
    
Yes, it is -- that's why I wrote "under popular derandomization assumptions." Specifically, we know that GI is in coAM. So if (as is widely conjectured) AM=NP, then GI is in coNP as well. –  Scott Aaronson Aug 25 '12 at 17:00

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.

share|improve this answer
2  
Using "et al." is evil, I put in the full citation. sbseminar.wordpress.com/2010/02/21/et-al-is-unethical –  Noah Snyder Jul 14 '10 at 18:20
8  
I never wrote this result up, but I posted some notes from a talk on this a while ago. math.uic.edu/~agol/coNP/coNP01.html The certificate is a taut sutured manifold hierarchy, and my notes don't describe the base case, which is quite complicated. I still plan to write this up some time, but due to the lack of proper dissemination, this should probably be downgraded to a conjecture. –  Ian Agol Jul 14 '10 at 18:51

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

  • The closest vector problem (CVP) asks, for a vector x ∈ ℝn, 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

  • GapCVPf(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;

  • GapSVPf(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 GapCVPn and GapSVPn 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.

share|improve this answer

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.

share|improve this answer

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)

share|improve this answer
    
Possibly a dumb question: Isn't this a promise problem and therefore not technically in NP or coNP? –  Harry Altman Jul 14 '11 at 21:52
    
Dear Harry, I dont know –  Gil Kalai Jul 15 '11 at 5:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.