Computation times of NP sets of different densities
From MaRDI portal
Publication:1348523
DOI10.1016/0304-3975(84)90111-7zbMath0985.68515MaRDI QIDQ1348523
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
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Restrictive Acceptance Suffices for Equivalence Problems, Upper bounds for the complexity of sparse and tally descriptions, On random reductions from sparse sets to tally sets, On sets polynomially enumerable by iteration, Almost everywhere high nonuniform complexity, Logarithmic advice classes, Polynomial-time compression, Succinctness as a source of complexity in logical formalisms, Listing graphs that satisfy first-order sentences, Locating \(P\)/poly optimally in the extended low hierarchy, Measure on \(P\): Strength of the notion, Complete distributional problems, hard languages, and resource-bounded measure, A Downward Collapse within the Polynomial Hierarchy