My favorite NP-complete problem!
summary
Claim: packaging Elmo’s World segments into uniform three-episode packages is exactly the classic exact cover by three sets problem (Karp 1972, aka X3C). Input: a fixed list of acceptable triples, each segment must appear exactly once, no overlaps allowed. Result: this instance is NP-complete so no efficient algorithm known to guarantee solutions for every case; the actual distribution teams end up failing or using heuristics and manual choices rather than a provable solver.
AI-written summary · about
chapters (6)
- 0:00Start
- 1:43Sorting
- 4:09Crossword
- 5:03Satisfiability
- 7:32Hamiltonian Cycle
- 13:13How Do You Pick the Groups of Three
related talks
34mSolving Problems Declaratively
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
47mExploiting Combinatorial Structure in Constraint Programming: ...
23mTowards Practical Distribution Testing
52mVariety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
38mSome Easy Optimization Problems Have the Overlap-Gap Property
43mEfficient Distance Estimation And Causal Inference For Discrete Models