Combinatorics of first order structures and propositional proof systems
From MaRDI portal
Publication:701740
DOI10.1007/s00153-003-0186-yzbMath1061.03060MaRDI QIDQ701740
Publication date: 16 December 2004
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-003-0186-y
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
03C07: Basic properties of first-order languages and structures
Related Items
LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE, Relativization makes contradictions harder for resolution, A note on propositional proof complexity of some Ramsey-type statements, Tight size-degree bounds for sums-of-squares proofs, The treewidth of proofs, Partially definable forcing and bounded arithmetic