Timeline for A language complete for NP intersection co-NP
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2017 at 2:21 | comment | added | Samuel Schlesinger | I think you might be thinking of the fact that if $NP \cap coNP$ has no complete problems then $P \neq NP$, which is because if we have our hypothesis and $P = NP$, we have that $P = NP = coNP = NP \cap coNP$ which has complete problems. | |
| Aug 8, 2010 at 6:39 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
added 343 characters in body; added 4 characters in body
|
| Aug 8, 2010 at 6:34 | comment | added | Ryan Williams | Marcos: there are many possible hypotheses that imply $PH$ collapses. Something like $NP = coNP$ would do it, or $NP = NP \cap coNP$. But complete languages for $NP \cap coNP$ aren't known to do it. I don't know of any interesting consequences of having complete languages for $NP \cap coNP$ other than what I put in my answer (which is unfortunately not much). | |
| Aug 8, 2010 at 6:27 | comment | added | Marcos Villagra | @Ryan: also, what would be the consequences of having complete problems for $NP\cap coNP$? | |
| Aug 8, 2010 at 6:26 | comment | added | Marcos Villagra | @Ryan: OK, I understand. Then, what do we need to proof collapsing in the polynomial hierarchy in general? | |
| Aug 8, 2010 at 6:15 | comment | added | Ryan Williams | Marcos: Of course $Sigma_2 P$ contains $NP$ and $coNP$. That does not mean "$NP \cap coNP$ has a complete language implies the polynomial hierarchy collapses". | |
| Aug 8, 2010 at 6:13 | comment | added | Peter Shor | One would think that any such reference would have to cite Hartmanis and Immerman: springerlink.com/content/w115v82352n00474 but I can't find one that does. | |
| Aug 8, 2010 at 6:05 | comment | added | Marcos Villagra | in the draft version, chapter 5, the polynomial hierarchy and alternations, page 5.2(92), where it says "Note that $\sum_2^p contains both the classes NP and coNP". There is no proof, but this implies that a complete problem collapses the hierarchy to the second level. | |
| Aug 8, 2010 at 6:01 | comment | added | Ryan Williams | Please tell me the page on which this is proved in Arora and Barak. | |
| Aug 8, 2010 at 5:54 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
added 149 characters in body; added 110 characters in body
|
| Aug 8, 2010 at 5:54 | comment | added | Ryan Williams | Got a reference?... | |
| Aug 8, 2010 at 5:48 | history | answered | Marcos Villagra | CC BY-SA 2.5 |