Question

Define reduction from problem x to problem y

Answer 1

A polynomial-time truth-table reduction from a problem x to a problem y (both decision problems) is a polynomial time algorithm for transforming inputs to problem x into a fixed number of inputs to problem y, such that the output for the original problem can be expressed as a function of the outputs for y.

HOPE IT'S HELP you