The Complexity of Decision Versus Search
From MaRDI portal
Publication:4286231
DOI10.1137/S0097539792228289zbMath0802.68052OpenAlexW1967415230MaRDI QIDQ4286231
Mihir Bellare, Shafi Goldwasser
Publication date: 27 April 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792228289
Cryptography (94A60) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the existence of subexponential parameterized algorithms, Probabilistic proof systems — A survey, The Journey from NP to TFNP Hardness, Deciding Parity Games in Quasi-polynomial Time, Unnamed Item, Many-one reductions and the category of multivalued functions, On efficiently solvable cases of quantum \(k\)-SAT, Cook versus Karp-Levin: Separating completeness notions if NP is not small, Upward separations and weaker hypotheses in resource-bounded measure, ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM, Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998, On pseudorandomness and resource-bounded measure, Does the polynomial hierarchy collapse if onto functions are invertible?, The opacity of backbones
