<p>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. [ <a href="http://www.cs.rit.edu/~cmh/10.1.1.88.9482.pdf" rel="nofollow noreferrer">as .pdf</a> ] 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$. </p>

<p>Also, we have <a href="https://cstheory.stackexchange.com/a/20645/495">strong reason</a> 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$. </p>

<hr>

<p><strong>Disclaimer:</strong> 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.</p>

CC BY-SA 3.0
2014-01-19T16:44:17.513Z
2014-01-19T16:44:17.513Z
2017-04-13T12:32:28.117Z
Thomas Klimpel
<p>I believe that there exists very space efficient high quality random number generators. Despite this belief, I normally use <a href="http://en.wikipedia.org/wiki/Mersenne_twister" rel="nofollow noreferrer">Mersenne twister</a> 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.</p>

<hr>

<p>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.</p>

<p>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.</p>

<hr>

<p><strong>Background</strong> 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 <a href="https://math.stackexchange.com/questions/96188/classifications-of-finite-nilpotent-groups">classification of finite nilpotent groups</a> 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.)</p>

CC BY-SA 3.0
2013-11-28T14:02:53.667Z
I'm not sure how this answer relates to the question. Could you elaborate?
Matthias
CC BY-SA 3.0
2013-11-28T16:20:36.180Z
@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.)
Thomas Klimpel
CC BY-SA 3.0
2013-11-28T16:32:26.300Z
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.
Matthias
CC BY-SA 3.0
2013-11-28T21:33:09.550Z
@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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up), I found the quoted result "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [ [HT03](https://complexityzoo.uwaterloo.ca/Zooref#ht03) ]. The paper is online, but I haven't read it (yet)...
Thomas Klimpel
CC BY-SA 3.0
2013-11-26T01:15:26.060Z
2014-01-19T16:44:53.297Z
2017-04-13T12:19:19.363Z
Thomas Klimpel
<p>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 <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/" rel="noreferrer">listed a few other candidate problems here</a>). </p>

<p>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 <em>Geometric Algorithms and Combinatorial Optimization,</em> and Schrijver makes similar statements in <em>Combinatorial Optimization: Polyhedra and Efficiency</em>. <a href="https://twitter.com/wjcook/status/508771136583524353" rel="noreferrer">This picture</a> makes it clear where Jack Edmonds stands on the issue.</p>

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

CC BY-SA 3.0
2013-11-23T05:42:08.903Z
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.
Joey Eremondi
CC BY-SA 3.0
2013-11-23T05:52:01.837Z
I was hoping for answers like [what Scott Aaronson gave for P versus NP](http://www.scottaaronson.com/blog/?p=122).
Austin Buchanan
CC BY-SA 3.0
2013-11-23T17:25:38.530Z
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.
vzn
CC BY-SA 3.0
2013-11-29T07:05:59.933Z
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](http://www.cs.rit.edu/~cmh/10.1.1.88.9482.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.
Thomas Klimpel
CC BY-SA 3.0
2013-12-28T14:29:34.030Z
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.
Peter Shor 
<cc.complexity-theory><np><conditional-results>
Reasons to believe $P \ne NP \cap coNP$ (or not)
Austin Buchanan
# Reasons to believe $P \ne NP \cap coNP$ (or not)

(Asked by: username_0 on 2013-11-23)

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](http://kintali.wordpress.com/2010/06/06/np-intersect-conp/)).

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](https://twitter.com/wjcook/status/508771136583524353) 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$?

**Tags:** cc.complexity-theory, np, conditional-results

> **Comments:**
> **username_1**: 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.  
> **username_0**: I was hoping for answers like [what Scott Aaronson gave for P versus NP](http://www.scottaaronson.com/blog/?p=122).  
> **username_2**: 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.  
> **username_3**: 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](http://www.cs.rit.edu/~cmh/10.1.1.88.9482.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.  
> **username_4**: 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.  

---

## 2 answers

### Answer by username_3 on 2014-01-19. Score: 5

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](http://www.cs.rit.edu/~cmh/10.1.1.88.9482.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](https://cstheory.stackexchange.com/a/20645/495) 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 by username_3 on 2013-11-26. Score: 0

I believe that there exists very space efficient high quality random number generators. Despite this belief, I normally use [Mersenne twister](http://en.wikipedia.org/wiki/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](https://math.stackexchange.com/questions/96188/classifications-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.)

> **Comments:**
> **username_5**: I'm not sure how this answer relates to the question. Could you elaborate?  
> **username_3**: @username_5 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.)  
> **username_5**: 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.  
> **username_3**: @username_5 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up), I found the quoted result "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [ [HT03](https://complexityzoo.uwaterloo.ca/Zooref#ht03) ]. The paper is online, but I haven't read it (yet)...  

---

