A note on propositional proof complexity of some Ramsey-type statements

DOI10.1007/s00153-010-0212-9zbMath1231.03050MaRDI QIDQ627444

Jan Krajíček

Publication date: 2 March 2011

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-010-0212-9

zbMATH Keywords

exponential lower bounds; resolution; Ramsey theorem; proof complexity

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F20: Complexity of proofs

Related Items

On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies, A lower bound on the size of resolution proofs of the Ramsey theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• Combinatorics of first order structures and propositional proof systems
• The relative complexity of NP search problems
• Lifting independence results in bounded arithmetic
• On the weak pigeonhole principle
• The provably total search problems of bounded arithmetic
• Herbrandizing search problems in Bounded Arithmetic
• Lower bounds to the size of constant-depth propositional proofs
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Computer Science Logic
• NP search problems in low fragments of bounded arithmetic
• Some remarks on the theory of graphs
• A new proof of the weak pigeonhole principle