Sparse sets in NP-P: EXPTIME versus NEXPTIME

DOI10.1016/S0019-9958(85)80004-8zbMath0586.68042OpenAlexW2090841650MaRDI QIDQ3711749

Vivian Sewelson, Juris Hartmanis

Publication date: 1985

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(85)80004-8

zbMATH Keywords

densityexponential timelower density sets in NPstructural properties of the sets in NP-Ptime-bounded complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (45)

In search of an easy witness: Exponential time vs. probabilistic polynomial time. ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ The isoperimetric spectrum of finitely presented groups ⋮ A downward translation in the polynomial hierarchy ⋮ A general method to construct oracles realizing given relationships between complexity classes ⋮ Separating classes in the exponential-time hierarchy from classes in PH ⋮ Limitations of the upward separation technique ⋮ Optimal proof systems imply complete sets for promise classes ⋮ Binary coded unary regular languages ⋮ Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations ⋮ 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 ⋮ On sets polynomially enumerable by iteration ⋮ The complexity of computing the number of strings of given length in context-free languages ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ Logarithmic advice classes ⋮ Non-deterministic exponential time has two-prover interactive protocols ⋮ On being incoherent without being very hard ⋮ Polynomial-time compression ⋮ Finite-model theory -- A personal perspective ⋮ Avoiding simplicity is complex ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ On the polynomial IO-complexity ⋮ The strong exponential hierarchy collapses ⋮ Reducibilities on tally and sparse sets ⋮ Exponential-time and subexponential-time sets ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ On the computational complexity of best Chebyshev approximations ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Tally NP sets and easy census functions. ⋮ Sparse sets and collapse of complexity classes ⋮ Kolmogorov characterizations of complexity classes ⋮ Towards the Actual Relationship Between NP and Exponential Time ⋮ \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

This page was built for publication: Sparse sets in NP-P: EXPTIME versus NEXPTIME