P vs NP asks: if we can check a solution fast, can we also find one fast?
Problems solvable quickly (polynomial time).
Solutions verifiable quickly.
The "hardest" problems in NP — a fast solution to one solves them all.
The question of whether efficiently checkable problems are also efficiently solvable controls the frontier of algorithms and security. P = NP would collapse verification into search and unsettle cryptography; P ≠ NP would certify intractability and justify the widespread use of heuristics, parameterization, and approximation.
NP consists of problems with polynomial‑length certificates verifiable in polynomial time; P is the subclass solvable outright. Polynomial‑time many‑one reductions compare difficulty, and NP‑complete problems are maximal under this ordering: solving one in polynomial time collapses NP to P. The lack of such algorithms motivates approximation, parameterized methods, and average‑case analysis.
Each clause becomes a group of literal-nodes; connect non-conflicting literals across clauses. A k-clique corresponds to a satisfying assignment (k = number of clauses).
Enter a small CNF formula and toggle variable assignments to see if it satisfies.
Allowed: x1..x9, ! (not), | (or), & (and), parentheses
Provide numbers and a target. We check if any subset matches the target.
Click nodes to cycle colors. No edge should connect same-colored nodes.
Match the reduction. Quick practice.
Note: This site offers educational intuition and small interactive demos; it does not constitute formal proofs.
Build a reduction pipeline and see size blowup and certificate mappings.
Compare greedy and exact solutions on tiny instances.
Explore hypothetical time laws under ETH/SETH style assumptions.