On Search Problems in Complexity Theory and in Logic (Abstract)

DOI10.1007/11758471_3MaRDI QIDQ3434537zbMATH OpenOpenAlexFDO

Authors Pavel Pudlák

Publication date 2 May 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11758471_3

Mathematics Subject Classification ID

Complexity of proofs (03F20) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Propositional proofs and reductions between NP search problems
• A note on the complexity of local search problems
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• scientific article; zbMATH DE number 1263206
• The relative complexity of NP search problems

Cited in

(9)

• The relative complexity of NP search problems
• Typical forcings, NP search problems and an extension of a theorem of Riis
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• Propositional proofs and reductions between NP search problems
• The NP search problems of Frege and extended Frege proofs
• Nested PLS
• scientific article; zbMATH DE number 2247430 (Why is no real title available?)
• On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus
• Note on constrained long choice with multiple beginning elements

This page was built for publication: On Search Problems in Complexity Theory and in Logic (Abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434537)