27
$\begingroup$

It seems that many people believe that $P \ne NP \cap coNP$, in part because they believe that factoring is not polytime solvable. (Shiva Kintali has listed a few other candidate problems here).

On the other hand, Grötschel, Lovász, and Schrijver have written that "many people believe that $P=NP\cap coNP$." This quote can be found in Geometric Algorithms and Combinatorial Optimization, and Schrijver makes similar statements in Combinatorial Optimization: Polyhedra and Efficiency. This picture makes it clear where Jack Edmonds stands on the issue.

What evidence supports a belief in $P\ne NP\cap coNP$? Or to support $P=NP\cap coNP$?

Improve this question
$\endgroup$
5
  • $\begingroup$ Define "reason." There's really no evidence one way or the other. This isn't something which can be tested experimentally. Until we have a proof one way or the other, the only "reasons to believe" it is gut feelings, either that some problem in $NP \cap coNP$ is not polynomial, or some gut instinct that they all are. $\endgroup$ – jmite Nov 23 '13 at 5:42
  • 2
    $\begingroup$ I was hoping for answers like what Scott Aaronson gave for P versus NP. $\endgroup$ – Austin Buchanan Nov 23 '13 at 5:52
  • 1
    $\begingroup$ many of the same aaronson ideas are applicable. disagree somwhat with jmite. there is lots of circumstantial evidence, including experimental evidence, some as listed by aaronson. $\endgroup$ – vzn Nov 23 '13 at 17:25
  • 5
    $\begingroup$ Theorem 3.1 of One-Way Permutations and Self-Witnessing Languages C. Homan and M. Thakur, Journal of Computer and System Sciences, 67(3):608-622, November 2003. [ as .pdf ] states that P≠UP∩coUP if and only if ("worst-case") one-way permutations exist. Theorem 3.2 recalls 10 further hypotheses that have been shown to be equivalent to P≠UP∩coUP. $\endgroup$ – Thomas Klimpel Nov 29 '13 at 7:05
  • 9
    $\begingroup$ I think factoring ∈ P is many, many orders of magnitude more likely than P = NP ∩ coNP, so that is certainly not the reason that I believe P = NP ∩ coNP. $\endgroup$ – Peter Shor Dec 28 '13 at 14:29
5
$\begingroup$

Theorem 3.1 of One-Way Permutations and Self-Witnessing Languages C. Homan and M. Thakur, Journal of Computer and System Sciences, 67(3):608-622, November 2003. [ as .pdf ] states that $P≠UP∩coUP$ if and only if ("worst-case") one-way permutations exist. Theorem 3.2 recalls 10 further hypotheses that have been shown to be equivalent to $P≠UP∩coUP$.

Also, we have strong reason to conjecture that $UP \ne NP$. Therefore, the above theorem and the conjecture result in a strong reason to believe that $P \ne NP ∩ coNP$.

Disclaimer: I moved Mohammad Al-Turkistany's edit of my answer to this community wiki answer. He believes that it perfectly answers the question since the existence of one-way permutations is widely believed. I myself haven't yet sufficiently understood the difference between "worst-case" and "average-case" one-way functions to claim that it really answers the question.

Improve this answer
$\endgroup$
0
$\begingroup$

I believe that there exists very space efficient high quality random number generators. Despite this belief, I normally use Mersenne twister in my code, which is high quality, but not very space efficient. There is a missing link between space efficiency and NP∩coNP, it's just a gut feeling that there is a link.

Let me try to give one reason why I believe that "true randomness" can be simulated/approximated very space efficiently. We know that it is possible to produce pseudo-random numbers that are sufficiently random for all practical purposes (including cryptography). We also know that using (a small amount of fixed) large prime numbers in the construction of pseudo-random number generators is rarely a bad idea. We know from conjectures like Riemann's that nearly all prime numbers contain a high degree of randomness, but we also know that we are not yet able to rigorously prove this.

Is there an intuitive explanation why the prime numbers behave like random numbers? The prime numbers are the complement of the composite numbers. The complement of a well behaved set is often more complicated than the original set. The composite numbers are composed of prime numbers, which in turn already gives this set a certain complexity.

Background I once tried to understand why P≠NP is difficult. I wondered whether approximating inner symmetry groups of a problem instance by nilpotent groups might not lead to an "abstraction algorithm" able to see into the inner structure of the problem instance. But then I realized that even computing the structure of a nilpotent group contains factoring as a special case. The question of the simple subgroups of a cyclic group of order n is equivalent to determining the prime factors of n. And the classification of finite nilpotent groups contains even worse subproblems related to graph isomorphism. That was enough to convince me that this approach won't help. But my next step was trying to understand why factoring is difficult, and the above answer is what I came up with. It was enough to convince me, so maybe it will also be convincing for other people. (I didn't know about groupoids or inverse semigroups back then, which are probably more suitable than nilpotent groups for handling inner symmetries. Still, the argument why such an approach won't be efficient stays the same.)

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ I'm not sure how this answer relates to the question. Could you elaborate? $\endgroup$ – Matthias Nov 28 '13 at 14:02
  • $\begingroup$ @Matthias The answer is the reason why I believe that P≠NP∩coNP. So the problem is probably not the relation to the question, but how to explain the reasoning. There is a form of mathematical platonism involved, which assumes that mathematical structures are able to model or approximate nearly everything that can exist in this world. True randomness is part of what can exist, and the answer tries to explain why there is a gut feeling that this randomness is already present in sufficiently space limited contexts to cause P≠NP∩coNP. (Sorry, perhaps I will improve/remove this comment later.) $\endgroup$ – Thomas Klimpel Nov 28 '13 at 16:20
  • 2
    $\begingroup$ Thanks. I guess I was wondering why the existence of space efficient high quality random number generators implies that P$\neq$NP$\cap$coNP, because I haven't heard that before. $\endgroup$ – Matthias Nov 28 '13 at 16:32
  • $\begingroup$ @Matthias I wrote "...missing link between space efficiency and NP∩coNP, it's just a gut feeling..." in the answer. I could try to elaborate, but I fear this wouldn't be well received. In fact, I guess you rather want independent references pointing in that direction instead of my own explanations. At the Complexity Zoo, I found the quoted result "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [ HT03 ]. The paper is online, but I haven't read it (yet)... $\endgroup$ – Thomas Klimpel Nov 28 '13 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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