CSE104, Lec 6: More NP-completeness reductions, clique, Hamiltonian Path, set cover
C. Seshadhri · 82:07
Once SAT/3SAT is NP-complete, polynomial-time reductions form a chain: any NP language reduces to 3SAT, and 3SAT reduces onward to Clique, quadratic equations, 0-1 integer programming, directed/undirected Hamiltonian...