Timeline for What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 1, 2012 at 16:23 | comment | added | user6976 | @Timothy: I am not sure which comment you are referring to. Yes, most CS people I know are trying to construct a one-way permutation. I think this is because trying to prove that there are none is completely hopeless. I may be wrong. Anyway, there is no proof either way, so this is pure speculation. There was time when thinking that the Earth is flat was pretty standard. | |
| Mar 1, 2012 at 15:55 | comment | added | Timothy Chow | @Mark: Are you losing the train of thought here? What I was addressing was which of NP ∩ Co-NP ≠ P and NP ∩ Co-NP = P is "more standard"; presumably that means "more widely believed." I'm confident that more people believe in the existence of one-way permutations (note: permutations and not functions) than don't. | |
| Feb 29, 2012 at 21:18 | comment | added | user6976 | @Emil: but the existence of a one-way function is as hard as anything else in that theory (where the number of conjectures greatly exceeds the number of theorems). I think the general idea is that any statement in that theory is either trivial or a "famous open problem". | |
| Feb 29, 2012 at 17:56 | comment | added | Emil Jeřábek | @Mark: To generalize Timothy’s comment, $NP\cap coNP\ne P$ is implied by the existence of one-way permutations. @Joel: I don’t think the existence of disjoint NP sets not separated by a $NP\cap coNP$ set is a standard assumption, nevertheless I’m pretty sure it’s an open problem, even assuming $NP\cap coNP\ne P$. | |
| Feb 29, 2012 at 16:13 | comment | added | user6976 | @Timothy: Some people think that factoring is in P. In fact some people believe that it is known to be in P, but the proof is highly classified. | |
| Feb 29, 2012 at 16:10 | comment | added | Timothy Chow | @Mark: NP ∩ Co-NP ≠ P is probably a little more standard because factoring (suitably formulated as a decision problem) is in NP ∩ Co-NP. | |
| Feb 29, 2012 at 15:53 | comment | added | Joel David Hamkins | I had understood Emil to be speaking of disjoint NP sets not separated by a set in P. My revised question is asking for disjoint NP sets not separated by a set in NP$\cap$Co-NP. But perhaps this also is simply an open question. I was imagining that one might undertake something like the argument I gave for the c.e. case, but with resource bounds. | |
| Feb 29, 2012 at 15:31 | comment | added | user6976 | I think Emil's comment means that what you ask now is also a standard complexity theory hypothesis. By the way, I am not sure what is more standard: whether NP $\cap$ Co-NP=P or $\cap$ Co-NP $\ne$ P. One of the main potential example, the primality, turned out to be in P. | |
| Feb 29, 2012 at 14:24 | comment | added | Joel David Hamkins | Thanks very much, Emil and Mark. I added a revised question, concerning separating sets in $\text{NP}\cap\text{Co-NP}$, rather than $P$, since I've realized that this is actually what I need for my intended use. | |
| Feb 29, 2012 at 14:12 | comment | added | Emil Jeřábek | The existence of inseparable disjoint NP pairs is considered a complexity assumption on its own, and it is not known to be implied by P ≠ NP. | |
| Feb 29, 2012 at 14:08 | comment | added | Joel David Hamkins | Yes, indeed! This seems to be the answer, although I suppose one could still hope to produce an example just from $P\neq NP$, instead of $P\neq NP\cap Co-NP$. | |
| Feb 29, 2012 at 13:58 | history | answered | user6976 | CC BY-SA 3.0 |