Reasons to believe $P \ne NP \cap coNP$ (or not)

Question

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

Answer 1

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.

Answer 2

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