Combinatorics of first order structures and propositional proof systems

DOI10.1007/s00153-003-0186-yzbMath1061.03060OpenAlexW1552145226MaRDI QIDQ701740

Jan Krajíček

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

zbMATH Keywords

complexity of proofsmodel-theoretic method

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) Basic properties of first-order languages and structures (03C07)

Related Items

Relativization makes contradictions harder for resolution, Tight size-degree bounds for sums-of-squares proofs, A note on propositional proof complexity of some Ramsey-type statements, Partially definable forcing and bounded arithmetic, The treewidth of proofs, LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE