np-completeness

NP-Completeness

Overview

NP-completeness answers whether an exact polynomial-time algorithm is plausible under the chapter model. Treat every proof as a certificate-and-reduction audit: define the decision language, prove verifiability, reduce from a known hard source in the correct direction, and prove both answer preservation and polynomial construction size.

Core principle: an NP-completeness proof is incomplete unless it separately proves membership in NP, maps arbitrary source instances to target instances without solving them, proves both directions of equivalence, and accounts for encoding length.

Shared CLRS Conventions

• Follow the parent clrs skill for mathematical formatting: every language definition, reduction relation, asymptotic bound, threshold, and symbolic assignment belongs in display LaTeX blocks.
• Keep tables verbal. Put reduction relations, targets, and construction formulas in display blocks near the table instead of inside table cells.
• Use elementary-graph-algorithms for ordinary graph traversal, shortest-paths for shortest-path algorithms, linear-programming for LP modeling, and this skill when the task asks for NP membership, NP-hardness, reductions, encoding, or exact hardness evidence.
• Do not announce that you are using this skill. Deliver the polished classification, reduction, or review directly.

When to Use

Use this skill when a task involves:

• proving a decision problem is in P, in NP, NP-hard, NP-complete, or related to co-NP;
• converting optimization hardness into a bound decision version;
• building or reviewing a polynomial-time reduction;
• choosing among CIRCUIT-SAT, SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP, or SUBSET-SUM as a source problem;
• checking whether a numeric algorithm is pseudo-polynomial rather than polynomial in the input length;
• explaining why an exact polynomial algorithm for one NP-complete problem would imply the standard collapse.

Do not use this skill merely because an algorithm is slow. Use it when the answer must reason about formal decision languages, certificates, reductions, or encoding-sensitive polynomial time.