CISC 462 — Lecture 15

NP

We'll begin by considering the notion of verifying a solution. In all of the problems we've studied so far, we were interested in solving them. But what if rather than solving a problem, someone claims to have a solution for the problem and you need to verify it? We will consider exactly this in the following problem.

A Hamiltonian path in a directed graph $G$ is a direted path that visits every node exactly once. Let $\mathrm{HAMPATH}$ be the problem of whether there exists a Hamiltonian path between $s$ and $t$ in a directed graph $G$.

It is not known whether $\mathrm{HAMPATH}$ is solvable in polynomial time. The brute force algorithm where we check every possible path is exponential. However, if someone claims that a graph has a Hamiltonian path, then we can check this very easily. All they'd have to do to convince us is give us the path they claim is Hamiltonian and we can check it.

A verifier for a language $A$ is an algorithm $V$, where $$A = \{ w \mid \text{$V$ accepts $\langle w,c \rangle$ for some string $c$}\}.$$ A polynomial time verifier is a verifier that runs in time polynomial in the length of $w$. We call the string $c$ the certificate for membership in $A$. Then length of a certificate is arbitrary, but for polynomial verifiers, $c$ will have polynomial length.

In the case of $\mathrm{HAMPATH}$, the certificate $c$ would be the Hamiltonian path in $G$ from $s$ to $t$.

However, note that if we wanted to show that a graph does not contain a Hamiltonian path, this is a different question. It is not as clear how you would try to convince someone that a graph doesn't contain a Hamiltonian path without simply iterating through all of the possibilities. In fact, there is no polynomial-time verifier for $\overline{\mathrm{HAMPATH}}$.

$\mathbf{NP}$ is the class of languages that have polynomial time verifiers.

This nomenclature seems a bit strange at first having characterized it in terms of verifiers. It makes more sense once we show that an equivalent characterization is via polynomial time solvability on nondeterministic Turing machines.

Theorem. A language is in $\mathbf{NP}$ if it is decided by some nondeterministic polynomial time Turing machine.

Proof. We show how to convert a polynomial time verifier into a polynomial time NTM and vice versa.

First, we show that we can simulate a polynomial time verifier with an NTM by guessing the certificate $c$. Let $A \in \mathbf{NP}$ and we construct an NTM $N$ to decide it. Let $V$ be a polynomial time verifier for $A$ and suppose it runs in time $n^k$. Then we construct $N$:

On input $w$ of length $n$: nondeterministically select string $c$ of length at most $n^k$.
Run $V$ on input $\langle w,c \rangle$.
If $V$ accepts, then accept; otherwise, reject.

To show the other direction, we assume $A$ is decided by a polynomial time NTM and construct a verifier $V$:

On input $\langle w,c \rangle$, where $w, c$ are strings, simulate $N$ on input $w$, treating each symbol of $c$ as a description of the nondeterministic choice to make at each step (as in the third tape in the DTM simulation of an NTM).
If this branch of the computation of $N$ accepts, accept; otherwise, reject.

$$\tag*{$\Box$}$$

Theorem. $\mathrm{HAMPATH}$ is in $\mathbf{NP}$.

Proof. We construct the following nondeterministic TM $N$ to decide $\mathrm{HAMPATH}$.

On input $\langle G,s,t \rangle$, where $G$ is a directed graph and $s,t$ are vertices, Write a list of $m$ numbers $p_1, \dots, p_m$, where $m$ is the number of nodes in $G$. Each number in the list is nondeterministically selected to be between $1$ and $m$.
Check for repeititons. If there are any, reject.
Check whether $s = p_1$ and $t = p_m$. If either are not, reject.
For $1 \leq i \leq m-1$, check whether $(p_i,p_{i+1})$ is an edge in $G$. If any are not, reject. Otherwise, all of the tests have passed, so accept.

Each step runs in time polynomial in the number of vertices in $G$, so this algorithm runs in nondeterministic polynomial time. $$\tag*{$\Box$}$$

We define the nondeterministic time complexity class $\mathbf{NTIME}(T(n))$ to be the collection of all languages that are decidable by an $O(T(n))$ time nondeterministic Turing machine.

This gives us the following corollary.

Corollary. $\mathbf{NP} = \bigcup_{k \geq 1} \mathbf{NTIME}(n^k)$.

A clique in an undirected graph is a subgraph where every two nodes are connected by an edge. A $k$-clique is a clique that contains $k$ vertices. The problem $\mathrm{CLIQUE}$ asks given a given graph $G$ and integer $k$, whether $G$ has a clique of size $k$.

Theorem. $\mathrm{CLIQUE}$ is in $\mathbf{NP}$.

Proof. The certificate $c$ is the clique, which is just the set of vertices in the clique. We simply test whether $G$ contains all of the edges between all of the nodes listed in $c$. Thus, $\mathrm{CLIQUE}$ is polynomial time verifiable.

To see that it's solvable in nondeterministic polynomial time, we simply nondeterministically choose a subset $c$ of $k$ vertices of $G$. We then test whether there are edges between the vertices we've chosen, which can be done in polynomial time. $$\tag*{$\Box$}$$

The $\text{SUBSET-SUM}$ problem asks, given a set of numbers $X = \{x_1, \dots, x_k\}$ and an integer $t$, whether there is a subset $S \subset X$ such that $$\sum_{s \in S} s = t.$$

Theorem. $\text{SUBSET-SUM}$ is in $\mathbf{NP}$.

Proof. To show that $\text{SUBSET-SUM}$ is verifiable in polynomial time, we choose the certificate $c$ to be the subset of our given set $X$ that adds up to $t$. Then we simply check that the numbers chosen in our certificate $c$ add up to $t$ and that they are actually members of $X$. This is clearly possible in polynomial time.

To solve this nondeterministically, we nondeterministically choose a subset $c$ of $X$. We test whether the members of $c$ add up to $t$ and accept if it does. This is doable in polynomial time. $$\tag*{$\Box$}$$