Dichotomization, reachability, and the forbidden subgraph problem(Extended Abstract)

摘要

We present several techniques for proving lower bounds that can be applied to problems about grammars, formal languages, program schemes, simple programming languages, and automata. These techniques include dichotomization, extensions of dichotomization to certain classes of relational problems, recursive analogues of the Post Correspondence Problem, and the reachability problem. These techniques provide many new lower bounds and provide a unified framework for viewing much of the work on the complexity of problems about grammars, languages, schemes, and automata. We show how to prove the undecidability of a problem by efficiently reducing the membership problem for Tms that always halt to it. We also introduce the forbidden subgraph problem.