HSE fall 2025, theory of computation, lecture 4: reductions

Polynomial time reductions, examples, NP-completeness, completeness of IND-SET, 3colorability, positive 1-in-3SAT, subsetsum Course website: http://wiki.cs.hse.ru/Theory_of_computation_2025