Towards separating nondeterminism from determinism

DOI10.1007/BF01744432zbMath0545.68038MaRDI QIDQ3334987

Ravindran Kannan

Publication date: 1984

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

nondeterminism versus determinismnondeterministic multitape Turing machinepolynomial time alternation complexity classeswell-behaving functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Limits on alternation trading proofs for time-space lower bounds ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Time-space tradeoffs for satisfiability ⋮ A time lower bound for satisfiability ⋮ Lower bounds on the complexity of recognizing SAT by Turing machines ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• On time-space classes and their relation to the theory of real addition
• A hierarchy for nondeterministic time complexity
• Alternation
• On Time Versus Space
• Separating Nondeterministic Time Complexity Classes
• On the Computational Complexity of Algorithms
• A Note Concerning Nondeterministic Tape Complexities