The Complexity of Decision Versus Search

DOI10.1137/S0097539792228289MaRDI QIDQ4286231zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(19)

• Probabilistic proof systems -- a survey
• Many-one reductions and the category of multivalued functions
• scientific article; zbMATH DE number 17813 (Why is no real title available?)
• Quantile and mean value measures of search process complexity
• Choice and complexity
• Deciding Parity Games in Quasi-polynomial Time
• 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
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Upward separations and weaker hypotheses in resource-bounded measure
• Decision making costs and problem solving performance
• On the complexity of the hidden subgroup problem
• On pseudorandomness and resource-bounded measure
• On quasilinear-time complexity theory
• On efficiently solvable cases of quantum \(k\)-SAT
• On efficiently solvable cases of quantum \(k\)-SAT
• Does the polynomial hierarchy collapse if onto functions are invertible?

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)