One such problem I know is integer factorization.

What are other interesting cases?

  • 2
    $\begingroup$ 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? $\endgroup$
    – Emil
    Jul 14, 2010 at 11:14
  • 6
    $\begingroup$ 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$. $\endgroup$
    – falagar
    Jul 14, 2010 at 11:30
  • $\begingroup$ Do other problems thought to be NP-Intermediate (en.wikipedia.org/wiki/NP-Intermediate) satisfy this? $\endgroup$
    – BlueRaja
    Jul 14, 2010 at 15:35
  • $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Jul 28, 2010 at 21:14
  • $\begingroup$ @Emil see also: cs.stackexchange.com/questions/9664/… I believe that a P-time reduction from FNP to NP via bisection is always possible for any problem. $\endgroup$ Jul 25, 2020 at 22:17

8 Answers 8


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

  • $\begingroup$ Here's a recent reference on simple stochastic games and related problems: springerlink.com/content/5500m01711124283. $\endgroup$
    – Peter Shor
    Jul 18, 2010 at 13:06
  • $\begingroup$ Presumably A and B are disjoint? $\endgroup$ Jul 19, 2010 at 7:25
  • 2
    $\begingroup$ Yes, the vertex set of the graph is the disjoint union of random nodes, "A" nodes, "B" nodes, and the two sinks. $\endgroup$
    – Peter Shor
    Jul 19, 2010 at 20:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis
    Jun 9, 2013 at 23:04
  • 1
    $\begingroup$ The link to springerlink.com in a comment above is broken, but the article can be found at doi:10.1007/978-3-642-10631-6_13 (Zbl 1272.91025). $\endgroup$ May 13 at 16:48

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

  • $\begingroup$ I thought whether GI is in coNP is an open problem? $\endgroup$
    – Turbo
    Dec 27, 2011 at 7:01
  • 6
    $\begingroup$ 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. $\endgroup$ Aug 25, 2012 at 17:00
  • $\begingroup$ is there an AM complete problem? $\endgroup$
    – Turbo
    Mar 30, 2017 at 9:56

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


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.

  • 5
    $\begingroup$ Using "et al." is evil, I put in the full citation. sbseminar.wordpress.com/2010/02/21/et-al-is-unethical $\endgroup$ Jul 14, 2010 at 18:20
  • 11
    $\begingroup$ 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. $\endgroup$
    – Ian Agol
    Jul 14, 2010 at 18:51
  • 3
    $\begingroup$ The same result, that unknottedness is in coNP, has now been published in: Lackenby, Marc (2021), "The efficient certification of Knottedness and Thurston norm", Advances in Mathematics, 387: 107796, arxiv.org/abs/1604.00290, doi.org/10.1016/j.aim.2021.107796 $\endgroup$ Jul 29, 2022 at 3:50

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.


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.

  • $\begingroup$ The link to sciencedirect.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ May 13 at 16:45

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)

  • $\begingroup$ Possibly a dumb question: Isn't this a promise problem and therefore not technically in NP or coNP? $\endgroup$ Jul 14, 2011 at 21:52
  • $\begingroup$ Dear Harry, I dont know $\endgroup$
    – Gil Kalai
    Jul 15, 2011 at 5:30
  • $\begingroup$ I believe that this is indeed a promise problem, since the set of Yes an No instances does not cover all possible inputs, and the complexity of recognizing that these are valid instances is not efficient (unless P=coNP) drops.dagstuhl.de/opus/volltexte/2015/4925 (If it were efficient to recognize the valid instances we could just use the ugly hack of defining the invalid instances as No to make a decision problem with the same complexity up to this reduction). $\endgroup$
    – dabacon
    Mar 24, 2015 at 4:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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