Defining NP: TMs and Verifiers

1. The "Lucky Guesser": Nondeterministic Polynomial Time

Let's start by revisiting a concept from earlier in the course: the Nondeterministic Turing Machine (NTM). An NTM is a TM that can have multiple possible next moves at any point. It accepts an input if any of its possible computation paths leads to an accept state.

You can think of an NTM as a "lucky guesser." At every choice point, it magically makes the best possible guess that will lead to an acceptance, if such a path exists.

This leads us to our first formal definition of NP. It mirrors the definition of P, but uses NTMs instead of deterministic TMs.

Definition: The Complexity Class NP (NTM version)
The complexity class NP is the set of all languages that can be decided by a Nondeterministic Turing Machine (NTM) in polynomial time.

Formally, we can express this as:
$\text{NP}={\bigcup }_{k\in \mathbb{N}}\text{NTIME}(n^k)$

Here, $\text{NTIME}(n^k)$ is the set of languages decidable by an NTM where every computational branch halts in $O(n^k)$ steps.

Example: The 3-SAT Problem

A classic problem in NP is 3-Satisfiability (3-SAT).

• Input: A Boolean formula in 3-Conjunctive Normal Form (3-CNF), which is an AND of clauses, where each clause is an OR of exactly three variables or their negations. For example: $(x_1\vee \neg x_2\vee x_3)\wedge (\neg x_1\vee x_2\vee x_4)$.
• Question: Is there an assignment of true/false values to the variables that makes the entire formula true?

A deterministic algorithm would need to try all $2^n$ possible assignments for $n$ variables, which is exponential. But an NTM can solve this in polynomial time.

As the video explained, the NTM algorithm for 3-SAT is:

1. Guessing (Nondeterministic): For each of the $n$ variables $x_1,\dots ,x_n$, nondeterministically guess a truth value (true or false). This takes $O(n)$ nondeterministic steps.
2. Checking (Deterministic): Substitute the guessed assignment into the formula and evaluate it. This takes time proportional to the formula's length, which is polynomial.

If there exists a satisfying assignment, one of the NTM's computation paths will guess it, the formula will evaluate to true, and the machine will accept. Since the entire process runs in polynomial time, 3-SAT is in NP.

2. The "Easy to Check" View: Polynomial-Time Verifiers

The NTM definition is powerful but can feel abstract. A more intuitive and practical way to think about NP is through the lens of verification.

Think about 3-SAT again. While finding a satisfying assignment is hard, if I give you a potential solution (e.g., "try $x_1=\text{true},x_2=\text{false},\dots$)", you can check if it works very quickly—just plug in the values and evaluate.

This proposed solution is called a certificate or a witness. The algorithm that checks the certificate is called a verifier.

Let's formalize what we saw in the video.

Definition: Verifier
A verifier for a language $L$ is an algorithm $V$ such that:
$L=\{w\mid \text{there exists a certificate }c\text{ such that }V\text{ accepts }⟨w,c⟩\}$
In other words, a string $w$ is in the language $L$ if and only if there is a certificate $c$ that the verifier $V$ can use to confirm it.

This leads to our second, equivalent definition of NP.

Definition: The Complexity Class NP (Verifier version)
The complexity class NP is the class of languages that have a polynomial-time verifier.

A verifier is "polynomial-time" if it runs in time polynomial in the length of the original input, $|w|$. An important consequence is that the certificate $c$ must also have a polynomial length, otherwise the verifier wouldn't even have time to read it.

3. The Equivalence of the Two Definitions

These two definitions—one based on nondeterministic machines and the other on deterministic verifiers—are equivalent. This is a fundamental theorem in complexity theory. A language is in NP if and only if it is decided by a polynomial-time NTM, and if and only if it has a polynomial-time verifier.

Let's briefly examine why this is true.

Let's summarize the logic from the notes.

Proof Sketch: Poly-time Verifier $⟹$ Poly-time NTM

If a language $L$ has a polynomial-time verifier $V$, we can build a polynomial-time NTM $N$ for it:

1. On input $w$, $N$ nondeterministically guesses a certificate $c$ of polynomial length.
2. $N$ then runs the deterministic verifier $V$ on the pair $⟨w,c⟩$.
3. If $V$ accepts, $N$ accepts.

The guessing part is the "N" in NTM, and the verification part is the "P" (polynomial time).

Proof Sketch: Poly-time NTM $⟹$ Poly-time Verifier

If a language $L$ is decided by a polynomial-time NTM $N$, we can build a polynomial-time verifier $V$ for it:

1. The certificate $c$ will be a string describing an accepting computation path of $N$ on input $w$. Since $N$ is poly-time, this path has a polynomial length.
2. The verifier $V$, on input $⟨w,c⟩$, deterministically simulates the single computation path of $N$ on $w$ that is described by $c$.
3. If this path ends in an accept state, $V$ accepts.

This shows that the two definitions are just different ways of looking at the same fundamental property.

Conclusion

Today we formally defined the immensely important complexity class NP. It captures a vast array of problems that we encounter constantly in computer science, from optimization to AI to logistics.

Key Takeaways:

• The class NP stands for Nondeterministic Polynomial time. It does not mean "non-polynomial".
• There are two equivalent, fundamental ways to define NP:
  1. The NTM Definition: NP is the class of decision problems solvable in polynomial time by a Nondeterministic Turing Machine (the "lucky guesser").
  2. The Verifier Definition: NP is the class of decision problems where a "yes" answer has a certificate that can be checked for correctness in polynomial time by a deterministic algorithm (the "easy to check" view).
• The equivalence of these definitions is a cornerstone of complexity theory, linking the abstract power of nondeterminism to the practical concept of efficient verification.

Preview of the Next Lesson:
We've now defined two major classes: P (efficiently solvable) and NP (efficiently verifiable). It's clear that P is a subset of NP (if you can solve a problem efficiently, you can certainly verify a solution efficiently—just solve it again and see if you get the same answer!). The biggest open question in theoretical computer science is whether P = NP. In our next lesson, we will explore this question and introduce the concept of NP-completeness—a set of the "hardest" problems in NP that hold the key to this monumental question.