Towards NP-P via proof complexity and search

MaRDI QIDQ3464626zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 27 January 2016

zbMATH Keywords

proof complexitysatisfiabilityproof searchCook's programproof automatizability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Recommendations

• Towards NP-P via proof complexity and search
• Twelve Problems in Proof Complexity
• scientific article; zbMATH DE number 1179974
• Proof Complexity of Non-classical Logics
• scientific article; zbMATH DE number 1860652

Cited in

(6)

• scientific article; zbMATH DE number 1263206 (Why is no real title available?)
• Towards NP-P via proof complexity and search
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Automata, Languages and Programming

This page was built for publication: Towards NP-P via proof complexity and search

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