---
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.
