Sparse sets in NP-P: EXPTIME versus NEXPTIME
From MaRDI portal
Recommendations
Cited in
(57)- On sets polynomially enumerable by iteration
- The complexity of computing the number of strings of given length in context-free languages
- Logarithmic advice classes
- On being incoherent without being very hard
- Polynomial-time compression
- Exponential-time and subexponential-time sets
- A note on sparse sets and the polynomial-time hierarchy
- Bridging across the (n) space frontier
- Succinctness as a source of complexity in logical formalisms
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- Space-efficient recognition of sparse self-reducible languages
- Computation times of NP sets of different densities
- A general method to construct oracles realizing given relationships between complexity classes
- Separating classes in the exponential-time hierarchy from classes in PH
- Optimal proof systems imply complete sets for promise classes
- Complete distributional problems, hard languages, and resource-bounded measure
- The isoperimetric spectrum of finitely presented groups
- On the reducibility of sets inside NP to sets with low information content
- On the computational complexity of best Chebyshev approximations
- Tally NP sets and easy census functions.
- Sparse sets and collapse of complexity classes
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- NL-printable sets and nondeterministic Kolmogorov complexity
- Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
- There are no sparse NP\(_{w}\)-hard sets
- scientific article; zbMATH DE number 3845567 (Why is no real title available?)
- Reducibilities on tally and sparse sets
- Limitations of the upward separation technique
- A Downward Collapse within the Polynomial Hierarchy
- Towards the Actual Relationship Between NP and Exponential Time
- scientific article; zbMATH DE number 1332663 (Why is no real title available?)
- scientific article; zbMATH DE number 1072529 (Why is no real title available?)
- scientific article; zbMATH DE number 1107624 (Why is no real title available?)
- On the sparse set conjecture for sets with low density
- On the cutting edge of relativization: the resource bounded injury method
- scientific article; zbMATH DE number 1834655 (Why is no real title available?)
- NL-printable sets and nondeterministic Kolmogorov complexity
- A downward translation in the polynomial hierarchy
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
- On the polynomial IO-complexity
- The strong exponential hierarchy collapses
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Binary coded unary regular languages
- Non-deterministic exponential time has two-prover interactive protocols
- Finite-model theory -- A personal perspective
- Converting binary automata to unary automata
- Avoiding simplicity is complex
- Binary coded unary regular languages
- The complexity of computing second solutions
- Kolmogorov characterizations of complexity classes
- New developments in structural complexity theory
- Downward translations of equality
- A result relating disjunctive self-reducibility to P-immunity
- 0-1 laws and decision problems for fragments of second-order logic
- On the complexity of ranking
- Bi-immunity results for cheatable sets
This page was built for publication: Sparse sets in NP-P: EXPTIME versus NEXPTIME
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3711749)
