Towards separating nondeterminism from determinism
From MaRDI portal
Publication:3334987
DOI10.1007/BF01744432zbMATH Open0545.68038MaRDI QIDQ3334987FDOQ3334987
Authors: R. Kannan 
Publication date: 1984
Published in: Mathematical Systems Theory (Search for Journal in Brave)
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
nondeterminism versus determinismnondeterministic multitape Turing machinepolynomial time alternation complexity classeswell-behaving functions
Cites Work
- On the Computational Complexity of Algorithms
- Alternation
- Separating Nondeterministic Time Complexity Classes
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- On Time Versus Space
- A hierarchy for nondeterministic time complexity
- A Note Concerning Nondeterministic Tape Complexities
- Title not available (Why is that?)
- On time-space classes and their relation to the theory of real addition
- Title not available (Why is that?)
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nondeterminism through well-founded choice
- Title not available (Why is that?)
- Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
- Title not available (Why is that?)
- 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)
