Comparing complexity classes

摘要

Complexity classes defined by time-bounded and space-bounded Turing acceptors are studied in order to learn more about the cost of deterministic simulation of nondeterministic processes and about time-space tradeoffs. Here complexity classes are compared by means of reducibilities and class-complete sets. The classes studied are defined by bounds of the order n, nk, 2n, 2nk. The results do not establish the existence of possible relationships between these classes; rather, they show the consequences of such relationships, in some cases offering circumstantial evidence that these relationships, do not hold and that certain pairs of classes are set-theoretically incomparable.