Complexity Theory Made Easy The Formal Language Approach to the Definition of Complexity Classes

摘要

In recent years generalized acceptance criteria for different nondeterministic computation models have been examined. Instead of the common definition where an input word is said to be accepted if in the corresponding computation tree an accepting path exists, more general conditions on this tree are used. We survey some recent results from this context, paying particular attention to nondeterministic finite automata as well as nondeterministic polynomial-time Turing machines.