NP and coNP

Polynomial certificates, their equivalence to nondeterministic computation, and the asymmetric evidence captured by NP and coNP.

Goals

• Move fluently between the nondeterministic-machine and verifier definitions of NP.
• Explain exactly why the certificate and verifier must have polynomial bounds.
• Read coNP as short evidence for universal/no claims, without treating it as “everything outside NP.”
• Prove the standard containments and recognize which separations remain open.

1. NP: search hidden inside verification

An NP question often has the form “does there exist a small object with an efficiently checkable property?” For SAT the object is an assignment; for CLIQUE it is a vertex set; for Hamiltonian Cycle it is an ordering of the vertices. A deterministic exhaustive search may inspect exponentially many candidates, but one proposed candidate can be checked quickly.

This does not say that NP means “not polynomial,” and it does not prove that any NP-complete problem is outside P. It says that yes-instances possess polynomially bounded evidence checkable in deterministic polynomial time.

The nondeterministic definition

A nondeterministic Turing machine $N$ accepts $x$ if at least one computation branch accepts. It decides a language in time $p(n)$ if every branch halts within $p(|x|)$ steps and

Thus

The quantifiers matter. On a no-instance, every branch must reject; swapping accept and reject would turn “some accepts” into “some rejects,” not into the required universal condition.

The verifier definition

A deterministic polynomial-time verifier is a machine $V(x,w)$ that receives the instance $x$ and a certificate $w$. A language $L$ is in NP iff there are polynomials $p,q$ and such a verifier satisfying

where $V$ halts in at most $q(|x|+|w|)$ steps on every pair. Some formulations require $|w|=p(|x|)$; padding a shorter certificate with a marked block makes the versions equivalent.

The certificate bound is essential. If $w$ could be exponentially long, merely reading it could take exponential time in $|x|$. The verifier’s runtime is polynomial in its actual input $|x|+|w|$; because $|w|\le p(|x|)$, composition gives a polynomial in $|x|$.

2. Why verifiers and NTMs are equivalent

Theorem (NP characterization). A language has a polynomial-time nondeterministic decider iff it has polynomial-size certificates checked by a deterministic polynomial-time verifier.

This is an equivalence, so it needs two constructions.

NTM $\Rightarrow$ verifier

Assume $N$ decides $L$ and every branch uses at most $c|x|^d$ steps. Encode one accepting branch by listing the nondeterministic choice made at each step. For a fixed machine, each transition choice needs only a constant number of bits, so the transcript has length at most $a c|x|^d$ for a machine-dependent constant $a$.

The verifier $V(x,w)$ deterministically simulates $N(x)$, forcing at each branching point the choice encoded by $w$. It rejects if a choice is illegal, the transcript ends incorrectly, or the simulated branch does not accept. It accepts exactly legal accepting transcripts.

• If $x\in L$, an accepting branch exists, and its transcript is an accepting certificate.
• If $x\notin L$, no accepting branch exists, so no transcript can make $V$ accept.
• Simulation takes polynomial time because the branch and transcript are polynomially long.

One may instead use a sequence of configurations as the certificate. That encoding is larger but still polynomial, and adjacent configurations are locally checkable.

Verifier $\Rightarrow$ NTM

Assume $V,p,q$ satisfy the verifier definition. On input $x$, the NTM computes $p(|x|)$, nondeterministically chooses that many certificate bits, and runs $V(x,w)$. It accepts iff $V$ accepts.

• If $x\in L$, some valid $w$ exists, hence one branch chooses it and accepts.
• If $x\notin L$, every possible $w$ is rejected, hence all branches reject.
• Guessing costs $p(|x|)$ steps; verification costs

which is polynomial because a composition and sum of polynomials remain polynomial.

This proof also clarifies “guess and check”: guessing is not random sampling. The NTM semantics existentially ranges over all certificates.

3. Worked certificate examples

SAT

For a CNF formula $\varphi$ over $n$ variables, $w\in\{0,1\}^n$ gives an assignment. Scan every literal and clause and accept iff every clause has a true literal. A straightforward implementation is polynomial in $|\langle\varphi\rangle|$.

For

$w=(1,1,0)$ certifies membership: the first clause is true through $x_1$, the second through $x_2$. A certificate that fails proves nothing; NP asks whether some certificate works.

CLIQUE

An instance is $(G,k)$, not just $G$. A certificate can list $k$ distinct vertices. Verify the range, distinctness, and each of the $\binom{k}{2}$ required edges. If $k$ is binary and larger than $|V|$, reject before trying to allocate $k$ objects. This small guard prevents a numeric parameter from hiding exponential work.

COMPOSITE

For a binary integer $N$, factors $a,b$ with $1<a,b<N$ and $ab=N$ form a certificate. Their binary lengths are $O(\log N)$ and grade-school multiplication is polynomial in bit length. This is a certificate for COMPOSITE, not automatically a certificate for PRIMES.

4. Complements and coNP evidence

For $L\subseteq\{0,1\}^*$, define

coNP is a class of languages; it is not the set-theoretic complement of the collection NP. A language can belong to both.

Applying the verifier characterization to $\overline L$ yields a useful quantifier view:

after complementing the verifier’s output. Equivalently, if $x\notin L$, there is a short witness exposing failure. This is why coNP is often described as efficiently checkable evidence for no-instances.

TAUT versus SAT

TAUT contains formulas true under every assignment. Its complement consists of formulas with a falsifying assignment. That assignment is a short NP certificate, so

UNSAT is likewise in coNP because its complement SAT is in NP. Notice the evidence asymmetry: one satisfying assignment establishes SAT; a failed search over a few assignments does not establish UNSAT.

A subtle but useful example

PRIMES is in P, and therefore in both NP and coNP. Historically, certificates for primality and compositeness illustrated that membership in $\mathrm{NP}\cap\mathrm{coNP}$ does not by itself imply a known deterministic algorithm; today primality is known to be in P. Always specify the integer encoding and how malformed strings are handled.

5. Containments and consequences

Proposition. $\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}$.

Proof walkthrough. A deterministic polynomial-time machine is an NTM with one branch, so $\mathrm P\subseteq\mathrm{NP}$. If $L\in\mathrm P$, take its total polynomial-time decider and swap accepting and rejecting states; this decides $\overline L$ in the same time. Hence $\overline L\in\mathrm P\subseteq\mathrm{NP}$ and $L\in\mathrm{coNP}$. $\square$

The same accept/reject swap does not prove NP closed under complement because nondeterministic acceptance is existential.

Proposition. If $\mathrm P=\mathrm{NP}$, then $\mathrm{NP}=\mathrm{coNP}$.

Proof. P is closed under complement. If NP equals P, NP inherits that closure. Thus $L\in\mathrm{NP}$ implies $\overline L\in\mathrm{NP}$, which is equivalent to $L\in\mathrm{coNP}$. Applying complement again gives the reverse containment. $\square$

Neither $\mathrm P\ne\mathrm{NP}$ nor $\mathrm{NP}\ne\mathrm{coNP}$ is currently known. A Venn diagram must therefore mark uncertain boundaries.

A particularly important consequence is:

If an NP-complete language $K$ is in coNP, then $\mathrm{NP}=\mathrm{coNP}$.

For every $A\in\mathrm{NP}$, $A\le_m^p K$. coNP is closed downward under polynomial many-one reductions, so $A\in\mathrm{coNP}$. Thus $\mathrm{NP}\subseteq\mathrm{coNP}$, and complementation gives equality. The closure proof is developed in the reductions lesson.

6. Encodings are part of the language

A language is a set of strings, so “the input is a graph” is shorthand for a chosen encoding. A robust decider first checks syntax. For malformed strings, choose and document a convention—normally reject. A reduction must also map malformed source encodings consistently, often to one fixed no-instance.

Numeric values are not unit-cost merely because they are written as one mathematical symbol. A binary integer $k$ occupies $\Theta(\log k)$ bits. An algorithm that performs $k$ iterations may therefore be exponential in input length unless a semantic guard such as $k\le |V|$ has already been established.

7. Three quantifier patterns worth separating

It helps to write the logical shape before searching for a certificate:

The predicate inside each bracket is polynomial-time computable. The first line directly has the NP verifier form. The second and third have the coNP form because a counterexample to membership is existentially witnessed. This syntactic comparison explains the evidence asymmetry without asserting a separation: perhaps a clever, non-obvious polynomial certificate for UNSAT exists, but proving that every coNP language has NP certificates is exactly the unresolved equality $\mathrm{NP}=\mathrm{coNP}$.

Graph problems show the same distinction. A proposed $k$-clique is immediately checkable, whereas “this graph has no $k$-clique” appears to quantify over all $k$-subsets. The latter language is in coNP because one clique refutes it. That observation alone neither proves nor disproves that it is also in NP.

A more explicit branch encoding

Suppose each configuration of $N$ has at most $b$ legal successors, where $b$ depends only on the fixed transition table. Number the choices $0,\ldots,b-1$ and let

For a $T(n)$-step computation, use exactly $rT(n)$ certificate bits, partitioned into $T(n)$ blocks. At step $t$, interpret block $t$ as a successor index. Reject if it denotes no legal successor. If $N$ halts early, require the remaining blocks to encode a designated padding move. This convention makes the verifier total and removes ambiguity about short transcripts. Its deterministic simulation stores the current configuration, looks up one transition, and updates it for at most $T(n)$ rounds.

Conversely, an NTM simulating a verifier need not materialize all $2^{p(n)}$ certificates. It branches once per guessed bit, creating a depth-$p(n)$ computation tree. Complexity measures the longest branch, not the total number of nodes in that tree. Each branch spends $p(n)$ steps guessing and then one polynomial verifier run. This is the precise reason exponentially many possible witnesses are compatible with nondeterministic polynomial time.

8. Consequences around complete languages

The statement “an NP-complete language $K$ is in coNP” has more force than merely placing one language in an intersection. For each $A\in\mathrm{NP}$ choose a reduction $f$ with

Because complementation preserves this same biconditional,

Now $K\in\mathrm{coNP}$ means $\overline K\in\mathrm{NP}$. Composing $f$ with an NP verifier for $\overline K$ proves $\overline A\in\mathrm{NP}$, hence $A\in\mathrm{coNP}$. Therefore $\mathrm{NP}\subseteq\mathrm{coNP}$. Taking complements gives the reverse inclusion.

This argument relies on many-one reductions. Their single output and biconditional make the complement step immediate. With other reduction notions, closure must be checked rather than assumed.

An analogous warning applies to NP-hardness: if $K$ is NP-hard but not known to lie in NP, then $K\in\mathrm{coNP}$ still implies $\mathrm{NP}\subseteq\mathrm{coNP}$ by downward closure. To call $K$ NP-complete, however, one must separately prove $K\in\mathrm{NP}$.

Common mistakes

1. “NP means exponential.” NP defines nondeterministic polynomial time, not a deterministic lower bound.
2. Swapping NTM accept/reject states. This changes existential acceptance incorrectly; it does not decide the complement.
3. Polynomial in the wrong quantity. Runtime must be polynomial in encoded input length, not numeric value.
4. Unbounded certificates. A fast verifier with exponentially long evidence does not establish NP membership.
5. Confusing a bad witness with a no-instance. A no-instance rejects every witness; one rejection is insufficient.
6. Drawing known strict containments. The boundaries among P, NP, and coNP are unresolved.

Exercises

Exercise 1 — $\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}$

Prove $\mathrm P\subseteq\mathrm{NP}$ and $\mathrm P\subseteq\mathrm{coNP}$. State what you did not prove about $\mathrm{NP}\cap\mathrm{coNP}$.

Exercise 2 — Hamiltonian-path certificate

Prove that the language of directed Hamiltonian paths is in $\mathrm{NP}$: define certificate, checks, completeness, and soundness.

Exercise 3 — coNP certificate for nontautology

Let $L$ be the language of formulas that are not tautologies. Prove $L\in\mathrm{NP}$, hence tautologies lie in $\mathrm{coNP}$.

Exercise 4 — Bounding $|w|$

Prove why a verifier definition must bound $|w|\le q(|x|)$. What breaks without the bound?

Exercise 5 — NP-complete language in $\mathrm P$

Prove: if some NP-complete language lies in $\mathrm P$, then $\mathrm P=\mathrm{NP}$.

Summary

$\mathrm{NP}$ is short efficiently checkable yes-evidence; $\mathrm{coNP}$ is no-evidence. Containments with $\mathrm P$ are known; the interesting equalities remain open.

Guided practice

Task 1 — Verifiers do not find certificates

Explain why a polynomial verifier need not find a certificate, and how that differs from a search algorithm.

Task 2 — Closure under complement

Prove $\mathrm P$ is closed under complement. Explain why the same proof fails for $\mathrm{NP}$ without extra assumptions.

Task 3 — $\mathrm{NP}\cap\mathrm{coNP}$

Give a natural problem historically associated with $\mathrm{NP}\cap\mathrm{coNP}$, and state what is known about the intersection.

Sources

Course evidence

• Current Semester A transcripts 7–8: certificate checking, nondeterministic computation, and the verifier/NTM characterization. No finer transcript line or timestamp locator is asserted here.
• Merged course summary, pp. 39–42: the core NP definitions, polynomial certificates, and verifier/nondeterministic-machine viewpoint.
• Merged course summary, pp. 81–85: complements, coNP, asymmetric evidence, and the NP-versus-coNP discussion. These page ranges are cited as course evidence; no wording is reproduced from the scanned summary.

Textbook verification

• Sipser, Introduction to the Theory of Computation, 3rd ed., §7.3, pp. 293–299: verifier definition of NP and equivalence with nondeterministic polynomial time.
• Arora–Barak, Computational Complexity: A Modern Approach (draft), §2.1–2.2, especially pp. 38–45 in the draft pagination: NP, certificates, and coNP.
• Papadimitriou, Computational Complexity, Ch. 9, pp. 181–187: NP certificates, nondeterminism, and complementary evidence. These references verify the standard claims; the sequencing and examples above follow the current course.