> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-3/advanced_topics/computational_complexity/np-completeness.md).

# NP-completeness

## Intro

A decision problem $$X$$ is NP-complete (NPC) if $$X \in NP$$ and $$X \in NP-hard$$.

## Certificate and Certifier

Algorithm $$C(s, t)$$ is a certifier for problem $$X$$ if $$\forall$$ string s, $$s \in X$$\
iff $$\exists$$ a string t (certificate) such that $$C(s, t) = yes$$.

Ex. 3-SAT\
Given a CNF formula $$\phi$$, is there a satisfying assignment?

* Certifier: 

  Check each clause in $$\phi$$ has least one true literal
* Certificate: 

  a solution (assignment to boolean variables) that

  satisfies $$\phi$$
* instance $$s$$:\
  $$\phi = (\overline{x\_1} \lor x\_2 \lor x\_3) \land (x\_1 \lor \overline{x\_2} \lor x\_3) \land (\overline{x\_1} \lor x\_2 \lor x\_4)$$
* certificate t:\
  $$x\_1 = true, x\_2 = true, x\_3 = false, x\_4 = false$$

## Reduction

A reduction from problem A $$\rightarrow$$ problem B is to construct a polynomial time algorithm that converts A inputs $$\rightarrow$$ equivalent B inputs (same yes/no answer).\
If we know how to solve B, then we know how to solve A. So if $$B \in P$$, then $$A \in P$$. If $$B \in NP$$, then $$A \in NP$$. B is at least as hard as A. (A $$\leq\_p$$B)

## Prove NPC

It's good to know so we can give up on searching a polynomial algorithm for this problem ᵔᴥᵔ. So how do we prove a problem $$X$$ is NP-complete?\
1\. $$X \in NP$$ (give a certificate and a ploy-time certifier)\
2\. reduce from a known NPC problem (3-SAT is a good choice for almost anything)

Cook and Levin did all the ground work to prove Circuit-SAT and 3-SAT are NPC. Here we are just gonna show NPC with reduction.

## Prove 3-SAT is NPC

We need a poly-time certifier to check a certificate of 3-SAT. Therefore, 3SAT $$\in NP$$.

Now we need to pick a known NPC problem and show 3-SAT is harder. We decide to reduce from Circuit-SAT to 3-SAT (Circuit-SAT $$\leq\_p$$3-SAT). We want to construct a poly-time algorithm that converts C-S inputs to 3-SAT inputs such that\
a 3-SAT instance $$\phi$$ is satisfiable iff the C-S inputs have an output of 1.

The conversion algorithm has 3 steps.

Reduction Proof\
Let $$K$$ be any circuit

$$\Leftarrow$$ there are inputs of $$K$$ that have output 1. can convert input values to create values at all nodes of $$K$$. This input satisfies $$\phi$$.

$$\Rightarrow$$ $$\phi$$ is satisfiable. 3-SAT clauses were designed to ensure the values assigned to all nodes in $$K$$ match exactly what the circuit would compute.

## Reference

Algorithm Design Chapter 8 [Intractability](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityII-2x2.pdf)