** 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*