Problems, encodings and certificates

What this concept is

An algorithm solves a specified problem over all valid inputs. Decision asks yes/no; search asks for a witness; optimization asks for the best feasible value or solution. Complexity is measured against encoded input length under a stated computation model.

Why it matters here

The earlier modules analyze algorithms. This module also asks what difficulty belongs to the problem and what a returned result actually certifies.

Concrete example

For a simple undirected graph G and integer k, Vertex Cover asks whether some set C of at most k vertices touches every edge. Checking a proposed C requires checking membership, size and every edge. A certificate can be encoded as vertex IDs with polynomial length. A fast verifier for a supplied set does not provide a fast method for finding one.

Common confusion / misconception

A feasible cover does not certify minimum size. Failure of one candidate does not prove no cover exists. The number W and the number of bits used to encode W are different input measures.

How to use it

Write the decision form beside the optimization form. For a cover C and a matching M (edges with disjoint endpoints), |M|≤OPT≤|C|. Every cover must touch each matching edge separately. When the bounds coincide, they certify optimality. For an edgeless graph both bounds are zero; report that case without a 0/0 approximation ratio.

Check yourself

For the path 0–1–2, verify cover {1} and matching {(0,1)}. Why do these certify the optimum?

Mini drill or application

Give a feasible but nonoptimal cover for the path. Then explain why a knapsack O(nW) DP is not necessarily polynomial in binary input length, reusing Module 1’s bit-cost argument.

Read this only if stuck

Use Erickson’s Algorithms and lecture notes for reductions and hardness, and the selective reading guide for the matching approximation. Full-book reading is not required.