scientific article; zbMATH DE number 1860652
From MaRDI portal
Publication:4790380
zbMath1049.03040MaRDI QIDQ4790380
Publication date: 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Mechanization of proofs and logical operations (03B35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (19)
On finding short resolution refutations and small unsatisfiable subsets ⋮ Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Proof complexity of modal resolution ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Towards NP-P via proof complexity and search ⋮ Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution ⋮ Cliques enumeration and tree-like resolution proofs ⋮ An improved time-space lower bound for tautologies ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Partially definable forcing and bounded arithmetic ⋮ Characterising tree-like Frege proofs for QBF ⋮ Understanding cutting planes for QBFs ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Unnamed Item ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle ⋮ Spines of random constraint satisfaction problems: definition and connection with computational complexity
This page was built for publication:
