np-completeness

Shows polynomial-time many-one reductions (<=_p) as moving “instance packets” along arrows: NP problems reduce to SAT (Cook–Levin), SAT reduces to 3-SAT, and NP-completeness as (in NP) + (every NP problem reduces to it). Final phase illustrates the key consequence: if A <=_p B and B is in P, then A would also be in P - polynomial-time solvability propagates backward through reductions.

canvasclick to interact

t=0s

practical uses

01.Designing hardness proofs by chaining known reductions (e.g., SAT -> 3-SAT -> your problem).
02.Reasoning about what it would mean to find a polynomial-time algorithm for an NP-complete problem (it would imply P=NP).
03.Classifying new problems as NP-complete by verifying NP membership and proving universal hardness via reductions.

technical notes

Single 4.2s cycle with 4 stages; eased motion of a blocky “packet” represents the instance transformation. Grid-snapped coordinates create a retro block aesthetic; subtle background grid and panel text are drawn with monospace fonts; all rendering uses the Canvas 2D API with provided GREEN/GREEN_DIM constants.

← network-flow bayesian-inference →