Next: Encoding and Algorithms
Up: Reducibility
Previous: Reducibility
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].
root
6/10/1998