Polynomial Verifiability
The Hamiltonian cycle problem illustrates an important phenomenon
called polynomial verifiability. Although no known algorithm can determine whether a Hamiltonian
cycle exists in polynomial time (the best known algorithms require exponential time), if someone hands us
a proposed cycle, we can verify that it is indeed a valid Hamiltonian cycle in polynomial time - simply by checking
that it visits every vertex exactly once.
Definition: Verifiability
A verifier for a language \(A\) is an algorithm \(V\) such that
\[
A = \{w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c\}.
\]
We measure the time of a verifier only in terms of the length of \(w\), so a polynomial time verifier runs
in polynomial time in the length of \(w\). A language \(A\) is polynomially verifiable if
it has a polynomial time verifier. The string \(c\) is called a certificate of membership in \(A\).
(In the context of the Hamiltonian cycle problem, the certificate can be a specific Hamiltonian cycle.)
Nondeterministic Polynomial Time (NP)
Definition: Class NP
NP is the class of languages that have polynomial time verifiers.
There is an equivalent characterization of NP using nondeterministic Turing machines (NTMs).
A language is in NP if and only if it is decided by some nondeterministic polynomial-time Turing machine.
The two definitions - polynomial-time verifier and nondeterministic polynomial-time decider - are equivalent.
Definition: Nondeterministic Time Complexity Class
\[
\text{NTIME}(t(n)) = \{L \mid L \text{ is a language decided by an } O(t(n))\text{-time nondeterministic Turing machine}\}.
\]
Equivalently,
\[
NP = \bigcup_k \text{NTIME}(n^k).
\]
P vs NP Question
- P is the class of languages for which membership can be decided in polynomial time.
- NP is the class of languages for which membership can be verified in polynomial time.
Problems like the Hamiltonian cycle are known to be in NP but are not known to be in P. Intuitively, it seems that
verifying a solution should be easier than finding one - but this has never been proved. The question of whether
\(P = NP\) or \(P \neq NP\) is one of the most important open problems in mathematics and computer science, listed among the
Clay Mathematics Institute's Millennium Prize Problems (with a \\($1\) million prize).
Most researchers believe that \(P \neq NP\).
What is known is the containment
\[
P \subseteq NP \subseteq \text{EXPTIME} = \bigcup_k \text{TIME}(2^{n^k}).
\]
Whether either inclusion is strict remains open.
NP-Completeness
Some problems in NP are as hard as any problem in NP - solving any one of them in
polynomial time would imply \(P = NP\). These are the NP-complete problems.
The Hamiltonian cycle problem is one such example.
Definition: Polynomial Time Reduction
Language \(A\) is polynomial time reducible to language \(B\), denoted
\[
A \leq_{P} B
\]
if a polynomial time computable function \(f: \Sigma^* \to \Sigma^*\) exists, where
\[
\forall w, \, w \in A \Longleftrightarrow f(w) \in B.
\]
The function \(f\) is called the polynomial time reduction of \(A\) to \(B\).
Here, a function \(f\) is polynomial-time computable if there exists a polynomial-time
Turing machine \(M\) that, on any input \(w\), halts with \(f(w)\) on its tape.
Definition: NP-Completeness
A language \(B\) is NP-complete if it satisfies the following two conditions:
- \(B\) is in NP.
- Every language \(A\) in NP is polynomial-time reducible to \(B\) (i.e., \(A \leq_P B\)).
A language satisfying condition 2 (but not necessarily condition 1) is called NP-hard.
Finally, we introduce the Hamiltonian cycle problem with weighted edges.
Example: Traveling Salesperson Problem (TSP) - Decision Version
Given a set of cities, the distances between them, and a number \(k\), is there a tour that visits each
city exactly once, returns to the starting city, and has total distance \(\leq k\)?
The decision version of TSP is NP-complete. The optimization version - which asks for the
shortest possible Hamiltonian cycle — is NP-hard but not NP-complete, because it is not
a decision problem and thus does not belong to NP in the formal sense.
Under the widely believed assumption that \(P \neq NP\), the landscape of complexity classes is as follows:
Note: If it were the case that \(P = NP\), then the classes P, NP, and NP-complete would all collapse
to the same class, since every nontrivial language in P would be NP-complete.
(\(P = NP = NP\text{-complete}\))
NP-completeness theory has profound practical implications: when faced with an NP-complete problem
in applications such as scheduling, routing, or resource allocation, we know that finding an exact
polynomial-time algorithm is almost certainly impossible. Instead, practitioners turn to
approximation algorithms, heuristics, and special-case solvers.
