Computation times of NP sets of different densities

DOI10.1016/0304-3975(84)90111-7zbMath0985.68515OpenAlexW2053392269MaRDI QIDQ1348523

Juris Hartmanis, Yaacov Yesha

Publication date: 13 May 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6388

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Listing graphs that satisfy first-order sentences, NL-printable sets and nondeterministic Kolmogorov complexity, Locating \(P\)/poly optimally in the extended low hierarchy, Isomorphisms and 1-L reductions, Measure on \(P\): Strength of the notion, On sparse oracles separating feasible complexity classes, On the relative complexity of hard problems for complexity classes without complete problems, Average-case intractability vs. worst-case intractability, P-immune sets with holes lack self-reducibility properties., Upper bounds for the complexity of sparse and tally descriptions, New developments in structural complexity theory, Kolmogorov complexity and degrees of tally sets, On the complexity of ranking, On sets polynomially enumerable by iteration, Almost everywhere high nonuniform complexity, New collapse consequences of NP having small circuits, Logarithmic advice classes, On random reductions from sparse sets to tally sets, Polynomial-time compression, NL-printable sets and Nondeterministic Kolmogorov Complexity, Dimension, entropy rates, and compression, The strong exponential hierarchy collapses, Error-bounded probabilistic computations between MA and AM, Some consequences of the existnce of pseudorandom generators, 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, Restrictive Acceptance Suffices for Equivalence Problems, An upward measure separation theorem

Cites Work

• Unnamed Item
• On sparse sets in NP-P
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• Tally languages and complexity classes