Separating Nondeterministic Time Complexity Classes

Cited in

(47)

k\(+1\) heads are better than k for PDAs
Dominoes and the complexity of subclasses of logical theories
On time-space classes and their relation to the theory of real addition
Bounded query machines: on NP and PSPACE
Some results on relativized deterministic and nondeterministic time hierarchies
Techniques for separating space complexity classes
Almost-everywhere complexity hierarchies for nondeterministic time
Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
On P-immunity of exponential time complete sets
Space hierarchy theorem revised.
Local reduction
On relationships between complexity classes of Turing machines
Some consequences of the existnce of pseudorandom generators
Sparse sets and collapse of complexity classes
Verifying whether one-tape Turing machines run in linear time
Average-case rigidity lower bounds
The minimum oracle circuit size problem
A time lower bound for satisfiability
A logical approach to locality in pictures languages
Nonuniform ACC circuit lower bounds
On the definitions of some complexity classes of real numbers
Towards separating nondeterminism from determinism
Universal quantifiers and time complexity of random access machines
Nonlevelable sets and immune sets in the accepting density hierarchy inNP
Classifying the computational complexity of problems
scientific article; zbMATH DE number 3604381 (Why is no real title available?)
Towards the Actual Relationship Between NP and Exponential Time
An application of the translational method
Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
On the cutting edge of relativization: the resource bounded injury method
An improved lower bound for the elementary theories of trees
Alternating time versus deterministic time: A separation
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
scientific article; zbMATH DE number 7250146 (Why is no real title available?)
Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
A Turing machine time hierarchy
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
Non-deterministic exponential time has two-prover interactive protocols
Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
Avoiding simplicity is complex
Bounded-depth succinct encodings and the structure they imply on graphs
Oblivious complexity classes revisited: lower bounds and hierarchies
A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
Deterministic two-way one-head pushdown automata are very powerful
Time hierarchies for cryptographic function inversion with advice
A uniform method for proving lower bounds on the computational complexity of logical theories
Relations between average-case and worst-case complexity

This page was built for publication: Separating Nondeterministic Time Complexity Classes

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