Noga Alon, Zvi Galil, et al.
FOCS 1992
Paper
Hierarchies of complete problems
Abstract
An attempt is made to present a framework for the diverse complete problems that have been found. A new concept-a Hierarchy of Complete Problems is defined. Several hierarchies in various domains such as graph theory, automata theory, theorem proving and games are established. © 1976 Springer-Verlag.