The Complexity of Decision Versus Search
From MaRDI portal
Publication:4286231
DOI10.1137/S0097539792228289zbMATH Open0802.68052OpenAlexW1967415230MaRDI QIDQ4286231FDOQ4286231
Authors: M. 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
Recommendations
Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (19)
- Title not available (Why is that?)
- Deciding Parity Games in Quasi-polynomial Time
- Decision making costs and problem solving performance
- On pseudorandomness and resource-bounded measure
- Quantile and mean value measures of search process complexity
- Upward separations and weaker hypotheses in resource-bounded measure
- Choice and complexity
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Does the polynomial hierarchy collapse if onto functions are invertible?
- Many-one reductions and the category of multivalued functions
- The journey from NP to TFNP hardness
- Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998
- The opacity of backbones
- On the existence of subexponential parameterized algorithms
- Probabilistic proof systems -- a survey
- On efficiently solvable cases of quantum \(k\)-SAT
- On efficiently solvable cases of quantum \(k\)-SAT
- On quasilinear-time complexity theory
- On the complexity of the hidden subgroup problem
This page was built for publication: The Complexity of Decision Versus Search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4286231)