Publication:4790380
From MaRDI portal
zbMath1049.03040MaRDI QIDQ4790380
Publication date: 2001
68Q25: Analysis of algorithms and problem complexity
03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03B35: Mechanization of proofs and logical operations
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Unnamed Item, Towards NP-P via proof complexity and search, On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances, An improved time-space lower bound for tautologies, Spines of random constraint satisfaction problems: definition and connection with computational complexity, On finding short resolution refutations and small unsatisfiable subsets, Cliques enumeration and tree-like resolution proofs, Understanding cutting planes for QBFs, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Partially definable forcing and bounded arithmetic, Quasipolynomial size proofs of the propositional pigeonhole principle, Propositional Proofs in Frege and Extended Frege Systems (Abstract), On the correspondence between arithmetic theories and propositional proof systems – a survey
