Suggest edit — coNP

Title

Name

Note

---
title: "coNP"
type: concept
related: [Conp, Unsat, Cook Levin Theorem]
source: https://www.jemoka.com/posts/kbhconp/
confidence: high
status: active
---

coNP is the set:
\begin{equation} \text{coNP}= \qty {\neg L \mid L \in NP} \end{equation}
&ldquo;$L$ is in coNP if there exists a poly-time verifier for the &ldquo;no&rdquo; instances of this language&rdquo;. Formally:
\begin{equation} L \in \text{coNP} \Leftrightarrow \exists \text{polytime} V s.t. x \in L: \exists w \in \qty {0,1}^{\text{poly}\qty(x)}, V\qty(x,w) = 1 \end{equation}
Some coNP stuff: UNSAT, NOT-3COL, etc.
$P \subseteq coNP$ Because we just invert the judgments after running $P$ to get the whole set.
Meaning: recall that $L \in P \implies \neg L \in P \implies \neg L \in NP \implies L \in coNP$.
&ldquo;Take $\text{P} \subseteq \text{NP}$, &lsquo;co&rsquo; both sides
if $\text{P}= \text{NP}$, then $\text{NP} = \text{coNP}$ \begin{equation} L \in \text{NP} \underbrace{\implies}_{\text{(given)}}\ L \in \text{P} \implies L \in \text{coNP} \end{equation}
More importantly, this means that $\text{NP} \neq \text{coNP}$ we see that the contrapositive of this statement implies $\text{P} \neq \text{NP}$.
coNP complete For every $A$ in coNP, there is a polynomial time reduction from $A$ to $B$ (that is, $B$ is coNP-hard)
UNSAT \begin{equation} \text{UNSAT} = \qty {\phi \mid \phi \text{ is a boolean formula and nothing satisfies $\phi$}} \end{equation}
try all and see that they all fail / not (something satisfies phi)
for $A \in coNP$, we show that $A \leq UNSAT$. For some input $w \in A$, we can reduce $w$ to some $\phi$ for $\neg A$ since $\neg A \in NP$ through Cook-Levin Theorem.
$w \in \neg A \implies \phi \in SAT$; meaning in particular $w \not\in \neg A \implies \phi \not\in SAT$; so $w \in A \implies \phi \in UNSAT$.
tautology \begin{equation} \text{TAUTOLOGY} = \qty {\phi \mid \phi \text{ is a boolean formula and every variable assignment satisfies $\phi$}} \end{equation}
in coNP directly: for all assignments of values, check that they accept complement: the complement of the language of non-trivial (i.e. there are some unsatisfying assignment) formulas in coNP-complete \begin{equation} \text{TAUTOLOGY} = \qty {\phi \mid \neg \phi \in \text{UNSAT}} \end{equation}
because we can just write a reduction $\text{UNSAT} \leq_{p} \text{TAUT}$ through simply inverting $\phi$ on an input.
FACTORING \begin{equation} \qty {(m,n) \mid m &gt; n &gt; 1\text{ are integers, there is a prime factor $p$ of $m$ where $n \leq p &lt; m$}} \end{equation}
if this is in $p$, we could probably break public-key cryptography currently in use.
Importantly, $\text{FACTORING} \in NP \cap coNP$. Factoring is in NP trivially because you can just give me the factors.
FACTORING is in coNP because the prime factorization of $m$ can be given to you $p_1 &hellip; p_{k}$; we can use PRIMES (below) to check that each $p$ is prime; then we can just look for the $p$ above $n$, then $(m,n)$ is in FACTORING, otherwise, it is not.
So both FACTORING is in NP, and not FACTORING is in NP, so FACTORING is in NP intersect coNP.
PRIMES \begin{equation} \text{PRIMES} = \qty {n \mid n\text{ is prime}} \end{equation}
this is in $P$
https://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf