Timeline for Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2015 at 2:10 | comment | added | Turbo | Since $\mathsf{3SAT}$ reduces to $\Pi$ which reduces to $\hat{\Pi}$, doesn't $\hat{\Pi}$ problem remain $\mathsf{NP}-\mathsf{complete}$? By definition $\hat{\Pi}\in\mathsf{NP}$, while since $\mathsf{3SAT}$ reduces to $\hat{\Pi}$ every problem in $\mathsf{NP}$ reduces to $\mathsf{3SAT}$ $\implies$ every problem in $\mathsf{NP}$ reduces to $\hat{\Pi}$. | |
| Apr 18, 2015 at 22:05 | history | answered | sdcvvc | CC BY-SA 3.0 |