Combinatorics of first order structures and propositional proof systems

DOI10.1007/S00153-003-0186-YzbMATH Open1061.03060OpenAlexW1552145226MaRDI QIDQ701740FDOQ701740

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

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

zbMATH Keywords

complexity of proofsmodel-theoretic method

Mathematics Subject Classification ID

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

Cited In (11)

• A transformation scheme for infinitary first-order combinatorics presenting computational level of expressiveness in predicate logic
• A logical approach to asymptotic combinatorics I. First order properties
• Partially definable forcing and bounded arithmetic
• A note on propositional proof complexity of some Ramsey-type statements
• The treewidth of proofs
• The Andrews-Curtis conjecture, term rewriting and first-order proofs
• Tight size-degree bounds for sums-of-squares proofs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Relativization makes contradictions harder for resolution
• LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE

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)