Complexity

NP

Class NP of problems: languages $L$ s.t. there exists a polynomial-time verifier $V$ satisfying

• if $x\in L$, then there exists a $y$ such that $V(x,y)$ accepts
• if $x\notin L$, then for all $y$ we have $V(x,y)$ must reject

where $x$ is the language of a specific problem and $y$ is any input that claims to be the solution to the problem.

• $\text{P}$ is known to be a subset of $\text{NP}$. This is simple to prove: we can still construct a verifier $V$ for a problem $\in \text{P}$, and verify a solution to be correct or incorrect in poly time.
• The additional bonus is that we can also find the solution in poly time.

Finding the perfect Matching of a graph is $\text{NP}$.

NP-complete

A problem $L$ is considered NP-complete when it satisfies two properties:

1. $L\in \text{NP}$.
2. For every other problem $L^{\prime }\in \text{NP}$, $L^{\prime }$ reduces to $L$.

If there were to exist a polynomial time algorithm for $L$, then we will have proved P = NP. This is because every other problem in NP can be reduced to $L$, meaning it can also be solved in polynomial time (assuming the transformation takes poly time).

In other words, if I can solve any of these NP-complete problems efficiently, then we’re able to solve all NP problems efficiently. This is why these problems are often referred to as “the hardest problems” to solve.

Proving NP-completeness

Proving NP is often trivial (construct a verifier). However, it is difficult to prove the second clause: showing that all NP problems reduce is difficult.

To simplify, we have a simple claim: assume that problem $A$ is NP-complete, and problem $B$ is in NP. Then, if we can reduce $A$ to $B$, then $B$ must also be NP-complete.

• Instead of proving all NP problems reduce to $B$, we only need to show that one NP-complete problem reduces to $B$.
• This requires us to already have a NP-complete problem. Historically, the Cook-Levin theorem showed the first proven NP-complete problem.

Cook-Levin Theorem

Boolean SAT is NP-complete.

Proof

This was the first NP-complete problem, so they did it the hard way. Showing that SAT is NP is trivial (the verifier $V$ just checks if the input combination resolves to true). To prove the second clause, we must describe a transformation $T$ from any arbitrary language $L\in \text{NP}$ to SAT.

For any arbitrary language $L\in \text{NP}$, from the definition we know there must exist a verifier $V(x,y)$.

• We can describe a circuit that executes the verifier.
• This circuit has to exist; after all, at the end of the day all our algorithms are being run on hardware circuits, and a verifier is the same.

Consider the transformation: $x,y\in \{0,1{\}}^{\ast }$. We encode the two inputs as a sequence of bits, and design a circuit that takes all the inputs and outputs exactly a single value: true if the verifier $V$ would have accepted, false if it would have rejected.

Here, the transformation $T$ is converting the verifier to a circuit.

We hardcode the input $x$ for this circuit $C$, let’s call it $C_{V(x,\cdot )}$. We now have two cases like before:

1. If $x\in L$, then there exists an input $y$ such that $V(x,y)$ accepts. In other words, there exists an input $y$ such that $C_{V(x,\cdot )}(T(y))=\text{true}$. So these two are equivalent.
2. If $x\notin L$, then for all inputs $y$, we have that $V(x,y)$ rejects. In other words, for all $T(y)$, we have that $C_{V(x,\cdot )}(T(y))=\text{false}$.

We’ve successfully shown how to reduce any NP problem into a circuit of its verifier, which is just the boolean SAT problem (where the inputs of the circuit are the different possible combinations). So if we find the correct combination of inputs such that the circuit evaluates to true, then we’ll also have found a solution for the original NP problem. Therefore, SAT is NP-complete.

I guess the hard part is actually specifying how we convert the verifier $V$ to this circuit. We sort of brushed over this in lecture… I assume it’s not easy.