Someone once told me:
I was not surprised when Linear Programming was in P since it was already in \( NP \cap coNP \), and problems in that intersection tend to be in P.
The same thing happened for PRIMALITY.
However FACTORING, viewed as the set
\( \{ (n,m) \colon \hbox{there is a factor of n that is } \le m \} \),
is in \( {\rm NP} \cap {\rm coNP} \). Is that indicative that FACTORING is in P? I do not think so, though that's backwards-since I already don't think FACTORING is in P, I don't think being in the intersection is indicative of being in P.
Same for DISCRETE LOG, viewed as the set
\( \{ (g,b,y,p) : \hbox{p prime, g is a gen mod p and } (\exists x\le y)[ g^x\equiv b \pmod p] \} \)
which is in \( {\rm NP} \cap {\rm coNP} \).
1) Sets in \({\rm NP} \cap {\rm coNP} \) but not known to be in P:
FACTORING- thought to not be in P, though number theory can surprise you.
DISCRETE LOG-thought to not be in P, but again number theory...
PARITY GAMES-thought to not be in P. (See Lance's post on the theorem that PARITY GAMES are in Quasi-poly time see here.)
Darn, only three that I know of. If you know others, then let me know.
2) Candidates for sets in \( {\rm NP} \cap {\rm coNP} \) but not known to be in P:
Graph Isomorphism. Its in NP and its in co-AM. Under the standard derandomization assumptions GI is in AM=NP so then GI would be in \( {\rm NP} \cap {\rm coNP} \). Not known to be in P. Is it in P? I do not think there is a consensus on this.
Darn, only one that I know of. If you know of others, then let me know, but make sure they are not in the third category below.
3) Problems with an \( {\rm NP} \cap {\rm coNP} \) feel to them but not known to be in P.
A binary relation B(x,y) is in TFNP if, B(x,y)\in P and, for all x there is a y such that
|y| is bounded by a poly in |x|
B(x,y) holds.
So these problems don't really fit into the set-framework of P and NP.
TFNP has the feel of \( {\rm NP} \cap {\rm coNP} \).
Nash Eq is in TFNP and is not known to be in P, and indeed thought to not be in P. There are other problems in here as well, and some complexity classes, and some completeness results. But these problems are not sets so not in the intersection. (I will prob have a future post on those other classes.)
--------------------------
So what to make of this? Why are so few problems in the intersection? Does the intersection = P (I do not think so)?
---------------------------
I close with another quote:
as a former recursion theorist I hope that \(NP \cap coNP\)=P, but as someone whose credit card numbers are on the web, I hope not.
Do promise problems count? If so, certain lattice problems like GapCVP or GapSVP are also candidates https://cims.nyu.edu/~regev/papers/cvpconp.pdf.
ReplyDeletePromise problems are in category 3- problems that have an NP cap coNP feel to them but are not sets so cannot be considered in NP cap coNP. But Good to know there are more in category 3!
DeleteThe unknot problem is known to be in NP and in coNP, but is not known to be in P.
ReplyDelete- Izzy Grosof
My favorite problem in 1) is ARRIVAL: https://link.springer.com/chapter/10.1007/978-3-319-44479-6_14.
ReplyDeleteDo we know or is it obvious whether the "beltway problem" of reconstructing the n exits of a beltway around a city, given only the n^2 inter-exit distances, is in co-NP? Similarly the turnpike problem.
ReplyDeleteI think the following is type 1. Given a "nice" unit disk graph (represented as an adjacency list), find the maximum clique (or a clique of size at least a given integer k). The definition of nice is that the graph can be realized with coordinates that are rational numbers of size polynomial in n. The coordinates are a certificate for both YES and NO, as given the coordinates the problem is in P. The nice condition is necessary because some unit disk graphs do not admit a model with polynomial coordinates. I don't know if people guess the problem is in P or not.
ReplyDeleteSimple stochastic games are known to be in NP ∩ coNP, but as far as I know, they are not known to be in P. See this paper: https://arxiv.org/abs/2009.10882
ReplyDeleteWhat do you think about this recent paper:
ReplyDeletehttps://arxiv.org/abs/2401.00747v4
which proposes a FPTAS to compute Nash Equilibrium (and hence PPAD=FP)?