An Introduction to Formal Languages and Automata, 7th Edition

14.6 POLYNOMIAL-TIME REDUCTION

One way to unify different cases is to see if we can reduce them to each other, in the sense that if one is tractable, the others will be tractable also.

DEFINITION 14.3

A language L₁ is said to be polynomial-time reducible to another language L₂ if there exists a deterministic Turing machine by which any w₁ in the alphabet of L₁ can be transformed in polynomial time to a w₂ in the alphabet of L₂ in such a way that w₁ ∈ L₁ if and only if w₂ ∈ L₂.

EXAMPLE 14.9

In the satisfiability problem we put no restriction on the length of a clause. A restricted type of satisfiability is the three-satisfiability problem (3SAT) in which each clause can have at most three literals. The SAT problem is polynomial-time reducible ...