The Complexity of Decision Versus Search

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

• Search Problems in the Decision Tree Model
• scientific article; zbMATH DE number 1263206
• The relative complexity of NP search problems
• Probabilistic checking of proofs
• \(p\)-Selective sets and reducing search to decision vs. self-reducibility

zbMATH Keywords

NP-completenesssparse setsprogram checkingself-reducibilityinteractive proofsquadratic residuosity

Mathematics Subject Classification ID

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)