Representing search problem as a decision problem Complexity of decision problems corresponding to search problems lemma Karp reduction (many-one reduction) definition Example Cook reduction (polynomial-time reduction) definition