Computability-and-Complexity 02

Equivalence of central open questions of search/decision problems theorem

Reductions

Reduction is a solution to the problem that uses a solution to some other problem. Proof of the equivalence of central open questions is built on reduction(s)

Karp reduction definition

Closure of Karp reduction under P lemma

Transitivity of Karp reduction lemma