next up previous contents
Next: Encoding and Algorithms Up: Reducibility Previous: Reducibility

A reducible to B means A at least as hard as B

Restricting our consideration to boolean problems has little impact on decidability, since many general problems are reducible to (at least as hard as) the yes-no problem. As an example, the yes-no problem of deciding the ambiguity of a context free grammar is called AMB. The general case of AMB called FIND (which produces a word with two or more parses) is reducible to AMB. Since no algorithm for AMB exists, no algorithm for FIND can exist [Hopcroft p. 178].