Suggest edit — UNSAT

Title

Name

Note

---
title: "UNSAT"
type: concept
related: [Np Complete]
source: https://www.jemoka.com/posts/kbhunsat/
confidence: high
status: active
---

\begin{equation} \text{UNSAT} = \qty {\phi : \text{all assignment make $\phi$ false}} \end{equation}
Equivalently, we have:
\begin{equation} \text{UNSAT} = \neg \text{SAT} \end{equation}
NP = coNP IFF UNSAT is in NP \begin{equation} \text{NP} = \text{coNP} \Leftrightarrow \text{UNSAT} \in \text{NP} \end{equation}
$\Rightarrow$ Because $\text{UNSAT} \in \text{coNP}$, and we hypothesize NP = coNP, so $\text{UNSAT} \in \text{NP}$
$\Leftarrow$ Suppose UNSAT in NP, we desire that $\text{coNP} = NP$. Let $L \in \text{coNP}$,so $\neg L \in \text{NP}$, since SAT is NP-complete, we can write that $L \leq_{p} \text{SAT}$. Equivalently, we have $L \leq_{p} \neg \text{SAT} = \text{UNSAT}$. Since $\text{UNSAT} \in \text{coNP}$, we have $L \in \text{NP}$.
In particular this proves that UNSAT is coNP-complete
coNP complete $L$ is coNP complete if
$L \in \text{coNP}$ $\forall A \in \text{coNP}, A \leq_{p} L$ key detail: $L$ is NP complete IFF $\neg L$ is coNP complete. Corollary: $L$ is NP-Complete IFF $\neg L$ is NP-Complete.