Comparing complexity classes

✍ Scribed by Ronald V. Book

• Book ID: 104148129
• Publisher: Elsevier Science
• Year: 1974
• Tongue: English
• Weight: 867 KB
• Volume: 9
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(74)80008-5

✦ Synopsis

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, n ~, 2 n, 2 n~. 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.