Polynomial time, certificates, and the class NP

Prerequisites: Algorithms, asymptotic analysis, graphs, and binary representations.

Learning objectives

• Define P and NP for decision problems.
• Design and bound a certificate verifier.
• Explain why input encoding changes complexity claims.

Complexity measures resources against input length

A decision problem asks for a yes or no answer. The class P contains decision problems solvable by a deterministic algorithm in time bounded by a polynomial in the input length. The input length is the number of symbols needed to encode the instance, not necessarily the numerical value of an integer inside it.

For a positive integer N written in binary, its representation uses about log2(N) bits. An algorithm performing N iterations is therefore exponential in that bit length, even though its loop count looks linear in the numeric value. Complexity statements need an encoding and a computational model. Polynomial time is a broad theoretical category, not a guarantee that an implementation is fast enough for every practical input.

A certificate makes a yes answer checkable

NP contains decision problems whose yes instances have polynomial-length certificates verifiable in polynomial time. The verifier receives both the instance and a proposed certificate. For a no instance, no allowed certificate may make it accept. NP does not mean “not polynomial,” and it does not require the verifier to discover the certificate.

Consider Hamiltonian path in a finite graph: does a path visit every vertex exactly once? A certificate is an ordered list of all vertices. Verify that its length is correct, each vertex appears exactly once, and every consecutive pair is an edge. With an appropriate graph representation, these checks are polynomial. A list that repeats a vertex is not a valid certificate even if every listed step follows an edge.

Finding such a path may require far more work than checking one supplied path. Enumerating all vertex orders is a possible but expensive search. The existence of a polynomial verifier does not establish a polynomial search algorithm. Every problem in P is in NP because a verifier can ignore the certificate and run the decider. Whether P equals NP remains an open question.

Translate optimization carefully

An optimization problem asks for the best feasible result rather than a Boolean answer. Its decision version often asks whether a result meeting a bound exists. For a route problem, this might ask whether there is a route of total cost at most B. A proposed route must establish both feasibility and the bound. Efficiently checking that a route is feasible does not by itself certify that it is globally optimal. An optimality claim needs additional evidence or an algorithm with a proved guarantee. Distinguish these claims when presenting benchmark results or accepting user-submitted solutions.

Practice problem

For the decision problem “does this graph have a vertex cover of size at most k?”, propose a certificate and a polynomial-time verifier. A vertex cover is a set touching every edge. Explain why verifying only that the certificate has at most k vertices is insufficient. State the conditions that must hold for yes and no instances. Then compare an algorithm that loops up to an integer weight W with the bit length of W, and explain why O(W) is not automatically polynomial in the encoded input length.

Worked solution

Use a list or set of chosen vertex identifiers as the certificate. Verify every identifier belongs to the graph, deduplicate or reject duplicates according to the certificate format, check the set size is at most k, and inspect every edge to ensure at least one endpoint is chosen. These checks are polynomial in the graph encoding length. Size alone would accept the empty set even when edges exist. Every yes instance has at least one accepting certificate; every no instance must reject every certificate. If W is encoded in b binary bits, W can be nearly 2^b, so O(W) iterations can be exponential in b. Algorithms polynomial in numeric magnitudes but not necessarily their binary encoding lengths are often called pseudopolynomial, and that distinction matters for weighted problems.

Check your understanding

What does membership in NP guarantee?

• Every instance can be solved quickly.
• Yes instances have polynomial-size certificates checkable in polynomial time.
• The problem has been proved outside P.

Explanation

NP is a verification class. It includes P, and whether all NP problems are in P is unresolved.

A loop performs N iterations for a binary-encoded positive integer N. Relative to its bit length b, the work can be what?

• Exponential, because N can be about 2^b.
• Always O(b).
• Independent of the encoding.

Explanation

Input length measures the representation. Numeric magnitude can be exponential in binary length.

Primary reading

• Automata, Computability, and Complexity: MIT OpenCourseWare

Open the study and save your work →