The Class NP

Given a verifier $v$, which is a TM (an algorithm) and a certificate $c$ (a string), can define a language as

L = {w | there exists a $c$ so that $v$ accepts <w, c>}

Intuitively, the certificate is the solution to the problem that w represents

NP = {L | L can be verified in polynomial time}

More precisely, there exists a verifier $v$ so that for every $<c, w>$ of length $N$, the verifier decides $<c, w>$ in $O(N^p)$ time, $p > 0$

Example 1: Hamiltonian Path

Naive: Try all N! permutations and verify them

$O(N^2 N!)$

def hampath_verifier(G, c)
    # O(EV) steps, which is about O(N^2), p=2
    # Given V vertices and E edges
    (verts, edges) = G
    is_valid = True
    for i in range(len(c)-1): # O(V)
        u = c[i]
        v = c[i+1]
        # Verify that (u, v) is an edge
        is_edge = False
        for e in edges: # O(E)
            if (u, v) is e:
                is_edge = True
        if not is_edge:
            is_valid = False
    if is_valid:
        accept
    else:
        reject

Example 2: Independent Set

A naive algorithm would try all subsets of size $k$ of the vertices and verify them

Suppose k = N/2

$O(N^3 N!/((N/2)!^2))$

def independentset_k_verifier(G, c):
    # Given V vertices and E edges
    # this goes through O(k^2 E) steps
    # Noting that k could actually be on the order of N
    # This is an O(N^3) verifier
    (verts, edges) = G
    is_valid = True
    for (u, v) in c x c: # O(k^2)
        for e in edges: # O(E)
            if (u, v) = e:
                is_valid = False
    return is_valid

Lemma: Every problem that's in P is in NP

Proof: A problem in $P$ can solved in polynomial time. A problems in NP if I can find a polynomial time verifier for it

Ex) L = {w#w | w is a string over alphabet}

def verify_P(w, c):
    # ignore the certificate c, and
    # solve the problem
    accept if the problem accepts # This runs in polynomial time
    reject if the problem rejects

$P \subset NP$

NP Stands for "Nondeterministic Polynomial"

Claim: A problem is in NP if it can be decided in polynomial time on a nondeterministic turing machine

To prove: A problem is in NP if and only if that problem can be decided in polynomial time by a NTM

First direction: Given a NTM M that decides $L$ in O(N^k), show that we can construct a $O(N^k)$ time verifier

A certificate identifies one branch of the NTM $M$'s computation. So we'll run the NTM just on that branch. Because NTM was polynomial time, then each branch runs in polynomial time, so therefore the branch corresponding to our certificate runs in $O(N^k)$ time.

Second direction: Given that we can verify in $L$ in $O(N^k)$ time, show that we can construct an NTM that decides in $O(N^k)$ time.

Nondeterministically select strings as inputs of length not more than $O(N^k)$, and run the verifier in parallel on each of these strings. And if one of the branches accepts, we accept the whole thing.

P = NP??

The general consensus is that hypothesis 1 is the correct one, but we're not 100% sure still after decades of work on this!