We have many problems, like factorization, that are strongly conjectured, but not proven, to be outside P. Are there any questions with the opposite property, namely, that they are strongly conjectured but not proven to be inside P?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ A reference request like yours is too broad for Stack Exchange -- you ask for a survey of a whole research area! You need to narrow your focus considerably before a question of reasonable scope appears. Try talking to your advisor(s), search with Google Scholar and check out this guide to better (re)searches on Academia. $\endgroup$– Raphael ♦Aug 29, 2016 at 9:00
-
$\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$– Raphael ♦Aug 29, 2016 at 9:00
-
$\begingroup$ You mean problems where noone knows if they are inside or outside P? $\endgroup$– NoDataDumpNoContributionAug 29, 2016 at 14:14
-
1$\begingroup$ There are such problems on certain subclasses of graphs; I'll try to add an answer later. $\endgroup$– JuhoAug 29, 2016 at 21:03
-
$\begingroup$ @Juho I'd be interested to see your answer $\endgroup$– Elliot GorokhovskySep 2, 2016 at 15:22
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
Two decades ago, one of the plausible answers would be primality testing: there were algorithms that ran in randomized polynomial time, and algorithms that ran in deterministic polynomial time under a plausible number-theoretic conjecture, but no known deterministic polynomial-time algorithms. In 2002, that changed with a breakthrough result by Agrawal, Kayal, and Saxena that primality testing is in P. So, we can no longer use that example.
I would put polynomial identity testing as an example of a problem that has a good chance of being in P, but where no one has been able to prove it. We know of randomized polynomial-time algorithms for polynomial identity testing, but no deterministic algorithms. However, there are plausible reasons to believe that the randomized algorithms can be derandomized.
For instance, in cryptography it is strongly believed that highly secure pseudorandom generators exist (e.g., AES-CTR is one reasonable candidate). And if that is true, then polynomial identity testing should be in P. (For instance, use a fixed seed, apply the pseudorandom generator, and use its output in lieu of random bits; it would take a tremendous conspiracy for this to fail.) This can be made formal using the random oracle model; if we have hash functions that can be suitably modelled by the random oracle model, then it follows that there is a deterministic polynomial-time algorithm for polynomial identity testing.
For more elaboration of this argument, see also my answer on a related subject and my comments on a related question.
$\begingroup$
$\endgroup$
3
It's a tough question, because there isn't a consensus. There are still people who conjecture that $P=NP$.
But in my mind, the most notable problem with a significant conjecture that it's in $P$ is Graph Isomorphism
But, again, nobody really knows.
In general, the "conjecture that it's in $P$ " is going to be rare. We only conjecture that a problem is in $P$ if we have no polynomial time algorithm for it already. But, not being able to find a $P$ algorithm for it, after all these years, is probably going to be seen more as "evidence" that the problem is hard, not easy.
-
$\begingroup$ I thought graph isomorphism was sitting tightly in close neighborhood of NP-C? $\endgroup$ Aug 29, 2016 at 14:29
-
1
-
$\begingroup$ As a slight generalization, even group isomorphism is not known to be in $\mathsf P$! it's known to be at most quasipolynomial, as graph isomorphism now is (thanks to Babai). $\endgroup$– wcharginNov 14, 2016 at 14:18
$\begingroup$
$\endgroup$
6
Although I'm not even close to be an expert in the field, I'd suppose that the unknotting problem is believed to be in P. It is known to be in $\sf NP\cap coNP$, and there are subexponential algorithms for it. More specifically, there is an algorithm which works $e^{O(\sqrt{n})}$, where $n$ is the number of crossings, see here. Note that another answer also indicates belief in the unknotting problem lying in $\sf P$.
-
1$\begingroup$ What's the evidence / reason to believe that the unknotting problem should be in P? There are lots of problems in NP $\cap$ coNP that have subexponential-time algorithms but that are believed to be unlikely to be in P, so if those are the only two relevant facts, that seems like a pretty weak reason to believe it should be in P. $e^{\sqrt{n}}$ is very far away from polynomial. $\endgroup$– D.W. ♦Aug 29, 2016 at 17:35
-
$\begingroup$ @D.W. Could you give an example of such a problem believed to be outside P? I don't know of any. $\endgroup$– WojowuAug 29, 2016 at 17:39
-
2$\begingroup$ Sure: factoring, discrete log. Or, finding an approximate Nash equilibirium of a two-player game, and others (see this comment from Scott Aaronson). Or, GapCVP, the gap version of the closest-vector problem for lattices, with appropriate parameters. $\endgroup$– D.W. ♦Aug 29, 2016 at 17:42
-
1$\begingroup$ en.wikipedia.org/wiki/…: "It is known to be in both NP and co-NP. This is because [...]" $\endgroup$– D.W. ♦Aug 29, 2016 at 17:46
-
1$\begingroup$ @D.W. Ah, that's indeed true. I see now how this invalidates my answer. I think I'm going to leave it anyways, but thanks for clarifying things! $\endgroup$– WojowuAug 29, 2016 at 17:49