Publication:4790380

zbMath1049.03040MaRDI QIDQ4790380

Toniann Pitassi, P. W. Beame

Publication date: 2001

zbMATH Keywords

computational complexity; circuit complexity

Mathematics Subject Classification ID

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, An Introduction to Lower Bounds on Resolution Proof Systems, Hardness Characterisations and Size-width Lower Bounds for QBF Resolution, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution, 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, Proof complexity of modal resolution, 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, Characterising tree-like Frege proofs for QBF, 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