Problems conjectured but not proven to be easy

Problem Detail: 

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?

Asked By : René G

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62985