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

interactive proofsNP-completenessprogram checkingquadratic residuosityself-reducibilitysparse sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cryptography (94A60)

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

(24)

• The relative complexity of NP search problems
• Quantile and mean value measures of search process complexity
• On the existence of subexponential parameterized algorithms
• The opacity of backbones
• On efficiently solvable cases of quantum \(k\)-SAT
• Does the polynomial hierarchy collapse if onto functions are invertible?
• Upward separations and weaker hypotheses in resource-bounded measure
• Many-one reductions and the category of multivalued functions
• scientific article; zbMATH DE number 17813 (Why is no real title available?)
• scientific article; zbMATH DE number 1048042 (Why is no real title available?)
• The journey from NP to TFNP hardness
• Search Problems in the Decision Tree Model
• On efficiently solvable cases of quantum k-SAT
• Probabilistic proof systems -- a survey
• Deciding Parity Games in Quasi-polynomial Time
• On the complexity of the hidden subgroup problem
• Choice and complexity
• 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
• Decision making costs and problem solving performance
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• On quasilinear-time complexity theory
• On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
• Just guess: improved (quantum) algorithm for the underdetermined MQ 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)