Towards separating nondeterminism from determinism

DOI10.1007/BF01744432MaRDI QIDQ3334987zbMATH OpenFDO

Authors R. 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)

Recommendations

• scientific article; zbMATH DE number 3846839
• scientific article; zbMATH DE number 3894449
• On the Succinctness of Nondeterminism
• Formal Techniques for Networked and Distributed Systems - FORTE 2005
• scientific article; zbMATH DE number 3980463
• Making Nondeterminism Unambiguous
• scientific article; zbMATH DE number 176517
• Nondeterminism within $P^ * $
• From determinism to quasideterminism in logic and beyond logic

Cites work

• scientific article; zbMATH DE number 3868616 (Why is no real title available?)
• scientific article; zbMATH DE number 3407150 (Why is no real title available?)
• A Note Concerning Nondeterministic Tape Complexities
• A hierarchy for nondeterministic time complexity
• Alternation
• On Time Versus Space
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• On the Computational Complexity of Algorithms
• On time-space classes and their relation to the theory of real addition
• Separating Nondeterministic Time Complexity Classes

Cited in

(14)

• Deterministic Turing machines in the range between real-time and linear-time.
• Lower bounds on the complexity of recognizing SAT by Turing machines
• A note on square rooting of time functions of Turing machines
• A time lower bound for satisfiability
• scientific article; zbMATH DE number 4145886 (Why is no real title available?)
• scientific article; zbMATH DE number 5917702 (Why is no real title available?)
• Nondeterminism through well-founded choice
• Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
• scientific article; zbMATH DE number 2102763 (Why is no real title available?)
• scientific article; zbMATH DE number 3846839 (Why is no real title available?)
• Limits on alternation trading proofs for time-space lower bounds
• Kolmogorov complexity and degrees of tally sets
• Time-space tradeoffs for SAT on nonuniform machines
• Time-space tradeoffs for satisfiability

This page was built for publication: Towards separating nondeterminism from determinism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3334987)