Polynomial-time reductions

Introduction

Introduction

Polynomial-time Turing reduction (the Cook reduction)

Solve using polynomial number of calls to another problem, and polynomial amount of time outside that.

Many-one reduction

Special case of the Cook reduction. Transform input of one problem to input of another, where answers are the same.

Transformation of inputs must be done in polynomial.

Truth table reduction

Another special case of the Cook reduction.

Transforms inputs into a number of other inputs to a different problem. Result is a function of the outputs of the other problem.