Timeline for What do we know about $NP \cap co-NP$?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 13, 2019 at 4:22 | comment | added | Cyriac Antony | I have heard statements like Problem A$\in $NP$\cap$co-NP means A cannot be NP-complete (assuming P$\neq$NP). How true is that? | |
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| May 7, 2015 at 22:06 | vote | accept | user6818 | ||
| Apr 22, 2015 at 12:11 | history | tweeted | twitter.com/#!/StackCompSci/status/590850400951136256 | ||
| Apr 17, 2015 at 22:40 | review | Close votes | |||
| Apr 18, 2015 at 11:17 | |||||
| Apr 17, 2015 at 22:31 | comment | added | user6818 | Isn't it better to club together related questions? I would think that the cohesion of ideas would be lost if I split it up. Thanks for the help BTW! | |
| Apr 17, 2015 at 22:25 | answer | added | D.W.♦ | timeline score: 9 | |
| Apr 17, 2015 at 22:23 | comment | added | D.W.♦ | Finally, what do you mean by "What do we know?" Would you count conditional results, such as "If $P \ne NP$, then ..." as a valid answer? Please flesh out your question. | |
| Apr 17, 2015 at 22:22 | comment | added | D.W.♦ | 1. What research have you done? There's lots known. 2. One question per question, please. "What do we know about $NP \cap coNP$?" is too broad a question for this site (see our help center). Asking several different questions is not suitable for this site -- we expect one question per question. Please identify one specific, answerable technical question, and ask that in this question -- you can post the other question separately in a separate question. But don't mash up 3 different questions together into the same post; that doesn't work so well with this site's format. | |
| Apr 17, 2015 at 22:14 | comment | added | Yuval Filmus | The Wikipedia pages on BPP and RP mentions that their connection to NP is unknown, and the same probably holds for ZPP as well. You can also check the complexity zoo. | |
| Apr 17, 2015 at 21:57 | comment | added | user6818 | Thanks! (1) So no decision questions of the kind I asked for in the second bullet point are known? (2) Any thoughts about the last bullet point? | |
| Apr 17, 2015 at 21:56 | history | edited | user6818 | CC BY-SA 3.0 |
added 16 characters in body
|
| Apr 16, 2015 at 23:44 | comment | added | Yuval Filmus | We can't separate NP from coNP since, as you mention, this would imply that P$\neq$NP. As far as I know, we also cannot conclude that NP$\neq$coNP from P$\neq$NP. | |
| Apr 16, 2015 at 23:02 | history | asked | user6818 | CC BY-SA 3.0 |