Timeline for Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?
Current License: CC BY-SA 3.0
13 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Dec 31, 2015 at 10:02 | history | tweeted | twitter.com/StackCSTheory/status/682502026048212992 | ||
Dec 23, 2015 at 9:00 | vote | accept | Turbo | ||
Dec 22, 2015 at 23:01 | history | edited | Turbo | CC BY-SA 3.0 |
added 16 characters in body
|
Dec 22, 2015 at 16:46 | history | edited | Turbo | CC BY-SA 3.0 |
added 15 characters in body
|
Dec 22, 2015 at 15:29 | vote | accept | Turbo | ||
Dec 23, 2015 at 8:51 | |||||
Dec 22, 2015 at 15:28 | history | edited | Turbo | CC BY-SA 3.0 |
added 174 characters in body
|
Dec 22, 2015 at 13:10 | history | edited | Turbo | CC BY-SA 3.0 |
added 65 characters in body
|
Dec 22, 2015 at 7:53 | vote | accept | Turbo | ||
Dec 22, 2015 at 15:23 | |||||
Dec 22, 2015 at 7:48 | answer | added | user6973 | timeline score: 7 | |
Dec 22, 2015 at 7:40 | comment | added | Thomas Steinke | If $\mathsf{BPP} \setminus (\mathsf{NP} \cup \mathsf{coNP}) \ne \emptyset$, then $\mathsf{BPP} \ne \mathsf{P}$. So the belief that $\mathsf{BPP}=\mathsf{P}$ rules out the possibility of finding $L \in \mathsf{BPP} \setminus (\mathsf{NP} \cup \mathsf{coNP})$. | |
Dec 22, 2015 at 5:38 | comment | added | Joshua Grochow | While it's true that it's possible that $\mathsf{NP} \cup \mathsf{coNP}$ could be contained in $\mathsf{BPP}$, if this is true then $\mathsf{NP}=\mathsf{RP}$ (exercise), and $\mathsf{PH}$ then collapses down to $\mathsf{BPP}$... | |
Dec 22, 2015 at 5:09 | history | edited | Turbo | CC BY-SA 3.0 |
added 67 characters in body
|
Dec 22, 2015 at 4:51 | history | asked | Turbo | CC BY-SA 3.0 |