TCS: Problems in P and NP

Problems in P and NP

Decision Versions of Computational Problems

A decision problem is a language of encodings of yes-instances. Encoding conventions determine the input length against which running time is measured

Search and optimization problems have related decision versions. For example, an optimization problem asks for a largest cut, while its decision version asks whether a cut of size at least $k$ exists

Graph Problems

Problem	Decision question	Relevant distinction
PATH	Does a directed path from $s$ to $t$ exist?	Solvable by graph search
SHORTEST-PATH	Is there an $s$ - $t$ path of cost at most $k$ ?	Nonnegative weights give standard polynomial algorithms
LONGEST-PATH	Is there a simple path with at least $k$ edges?	A simple path cannot repeat vertices
HAM-CYCLE	Is there a cycle visiting every vertex exactly once?	A permutation certifies a yes-instance
VERTEX-COVER	Can at most $k$ vertices cover every edge?	Choosing the vertices is the search task
MAX-CUT	Can a vertex partition cut at least $k$ edges?	A partition certifies the threshold

The word simple matters for longest path: allowing arbitrary repetition produces a different problem. Similarly, a Hamiltonian cycle visits every vertex, while an Eulerian cycle uses every edge

Minimum cut and maximum cut are different optimization problems. Polynomial-time algorithms for maximum flow and minimum cut do not supply such algorithms for maximum cut

Boolean Formulas

A literal is a variable or its negation. A CNF formula is a conjunction of clauses, each a disjunction of literals

\varphi=(x_1\lor\neg x_2)\land(x_2\lor x_3\lor\neg x_4)

SAT asks whether some assignment makes $\varphi$ true. In 3-SAT every clause has at most three literals; permitting repeated literals gives the usual exactly-three formulation as well

For 2-SAT, a clause $(a\lor b)$ becomes two implications

\neg a\to b \qquad \neg b\to a

Build the implication graph on literals. The formula is satisfiable exactly when no variable and its negation lie in the same strongly connected component. Strong connectivity gives a polynomial-time algorithm

For the converse direction, contract the strongly connected components to a DAG and assign literals according to a compatible ordering, ensuring that every implication is respected

Arithmetic and Input Length

An integer $N$ written in binary occupies $\Theta(\log N)$ bits. Trial division through $\sqrt N$ candidates is therefore exponential in the bit length, even though the bound looks polynomial in the value of $N$

Primality and compositeness have deterministic polynomial-time algorithms. Factoring asks for actual factors and is a search problem; its decision formulations must be specified before assigning them a decision complexity class

Graph isomorphism asks whether a vertex permutation preserves adjacency. A proposed permutation can be checked efficiently, regardless of the difficulty of finding one

Efficient Verification

Many problems have short evidence for a yes-answer: a satisfying assignment, a path, a cut, or a vertex permutation. Checking the evidence can be easier than searching for it

A language $L$ belongs to $\mathrm{NP}$ if there are a polynomial $p$ and a deterministic polynomial-time verifier $V$ such that

x\in L\quad\Longleftrightarrow\quad\exists y\in\{0,1\}^{\le p(|x|)}:\ V(x,y)=1

The string $y$ is a certificate or witness

Both requirements matter: the certificate must have polynomial length, and the verifier must run in polynomial time. A certificate containing an entire exponentially long computation is not a polynomial certificate merely because its adjacent steps are easy to check

Examples of Verifiers

For SAT, evaluate the formula on the proposed assignment
For HAM-CYCLE, check that the proposed vertex sequence is a permutation and that consecutive vertices, including the last and first, are adjacent
For VERTEX-COVER, check the size of the proposed set and inspect every edge
For MAX-CUT, label each vertex with a bit and count edges whose labels differ
For graph isomorphism, check that the proposed map is bijective and preserves adjacency in both directions

For every no-instance, all candidate certificates must be rejected. A verifier accepts a language through an existential condition, not by accepting a random certificate with high probability

Nondeterministic Polynomial Time

A nondeterministic machine has several possible transitions. It accepts when at least one computation branch accepts

\mathrm{NP}=\bigcup_{k\ge1}\operatorname{NTIME}(n^k)

The polynomial time bound applies to every branch

The machine can nondeterministically guess a certificate of polynomial length and run a deterministic verifier, proving that verification implies nondeterministic computation

Conversely, a certificate can list the transition choices of a polynomial-length accepting branch. A deterministic verifier follows those choices and checks whether the branch accepts

This equivalence explains the name: NP means nondeterministic polynomial time

P, NP and coNP

A deterministic polynomial-time decider is also a verifier that ignores its certificate, so

\mathrm P\subseteq\mathrm{NP}

Define the complement class by

\mathrm{coNP}=\{L:\overline L\in\mathrm{NP}\}

Thus UNSAT belongs to $\mathrm{coNP}$ , because its complement SAT has short certificates for satisfiability. Membership of UNSAT in $\mathrm{NP}$ would require short, efficiently checkable evidence of unsatisfiability for every unsatisfiable formula

Deterministic deciders can swap their two answers, so $\mathrm P$ is closed under complement and

\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}

The analogous operation does not complement a nondeterministic language: changing accepting branches to rejecting branches exchanges an existential condition with another existential condition, rather than the universal condition needed for the complement

\mathrm P=\mathrm{NP}\quad\Longrightarrow\quad\mathrm{NP}=\mathrm{coNP}

The converse implication has not been established

Every NP language can be decided deterministically by enumerating all polynomial-length certificates. Therefore

\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}

The time hierarchy separates $\mathrm P$ from $\mathrm{EXP}$ , but it does not locate $\mathrm{NP}$ strictly between them. The next lecture introduces complete problems that capture the difficulty of all NP verification tasks

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。