A complexity gap for tree resolution

DOI10.1007/s00037-001-8194-yzbMath0994.03005OpenAlexW2726059329MaRDI QIDQ1601038

Søren Riis

Publication date: 17 June 2002

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-001-8194-y

zbMATH Keywords

satisfiabilitypropositional proof complexitycombinatorial principlesgap phenomenonhard propositional tautologiesinfinite mathematical theoriestree-resolution proofs

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity of proofs (03F20)

Related Items (15)

Relativization makes contradictions harder for resolution ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Parameterized proof complexity ⋮ Towards a unified complexity theory of total functions ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ A combinatorial characterization of resolution width ⋮ Cutting Planes and the Parameter Cutwidth ⋮ Cutting planes and the parameter cutwidth ⋮ Partially definable forcing and bounded arithmetic ⋮ The treewidth of proofs ⋮ Resolution Width and Cutting Plane Rank Are Incomparable ⋮ Resolution and the binary encoding of combinatorial principles ⋮ On the Chvátal rank of the pigeonhole principle ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE

This page was built for publication: A complexity gap for tree resolution