Separating Nondeterministic Time Complexity Classes

Cited in

(47)

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

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)