Suggest edit — What Happens if P=NP?

Title

Name

Note

---
title: "What Happens if P=NP?"
type: concept
source: https://www.jemoka.com/posts/kbhwhat_happens_if_p_np/
confidence: high
status: active
---

&hellip;what can we solve efficiently?
the &ldquo;easy&rdquo; cases by definition all NP/NP Complete problems&hellip;
SAT 3COL Hamiltonian path problem and also anything in coNP because if \(\text{P}= \text{NP}\), then \(\text{NP} = \text{coNP}\) UNSAT NOT-3COL &hellip; review: certificates definition of NP, coNP \(L \in \text{NP}\) IFF \(\exists\) polytime verifier \(V\) such that \(x \in L \Leftrightarrow \exists w \in \qty {0,1}^{\text{poly}\qty(|x|)}, V\qty(x,w) = 1\)
\(L \in \text{coNP}\) IFF \(\exists\) polytime verifier \(V\) such that \(x \in L \Leftrightarrow \forall w \in \qty {0,1}^{\text{poly}\qty(|x|)} V\qty(x,w) = 1\)
notice how this difference exists only between existential vs universal quantifier (we got here to the expression coNP above by thinking of it as \(x \not \in L \Leftrightarrow \exists w \qty {0,1}^{\text{poly}\qty(|x|)} V\qty(x,w)=1\), and the negating this statement)