Combinatorics of first order structures and propositional proof systems

DOI10.1007/S00153-003-0186-YMaRDI QIDQ701740zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A finite-model-theoretic view on propositional proof complexity
• scientific article; zbMATH DE number 7204319
• The Complexity of Propositional Proofs
• scientific article; zbMATH DE number 1179974
• Propositional proof systems, the consistency of first order theories and the complexity of computations

Cited in

(12)

• A logical approach to asymptotic combinatorics I. First order properties
• The Andrews-Curtis conjecture, term rewriting and first-order proofs
• Tight size-degree bounds for sums-of-squares proofs
• The treewidth of proofs
• Partially definable forcing and bounded arithmetic
• A transformation scheme for infinitary first-order combinatorics presenting computational level of expressiveness in predicate logic
• scientific article; zbMATH DE number 1688382 (Why is no real title available?)
• Relativization makes contradictions harder for resolution
• scientific article; zbMATH DE number 1907992 (Why is no real title available?)
• Expansions of pseudoinfinite structures and circuit and proof complexity
• Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
• A note on propositional proof complexity of some Ramsey-type statements

This page was built for publication: Combinatorics of first order structures and propositional proof systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q701740)