Partially definable forcing and bounded arithmetic

DOI10.1007/s00153-014-0398-3zbMath1382.03090OpenAlexW2134910373MaRDI QIDQ2257103

Moritz Müller, Albert Atserias

Publication date: 23 February 2015

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

Full work available at URL: http://hdl.handle.net/2117/27193

zbMATH Keywords

forcingbounded arithmeticproof complexity

Mathematics Subject Classification ID

Logic in computer science (03B70) Nonstandard models of arithmetic (03H15) Other aspects of forcing and Boolean-valued models (03E40) Complexity of proofs (03F20) Model-theoretic forcing (03C25)

Related Items (2)

Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ The treewidth of proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• Combinatorics of first order structures and propositional proof systems
• Forcing, arithmetic, division rings
• Simplified lower bounds for propositional proofs
• An oracle builder's toolkit
• A complexity gap for tree resolution
• Some remarks on lengths of propositional proofs
• A combinatorial characterization of resolution width
• Proofs as Games
• Lower bounds for bounded depth Frege proofs via Pudlák-Buss games
• Forcing and reducibilities
• Polynomial size proofs of the propositional pigeonhole principle
• Approximation and Small-Depth Frege Proofs
• Forcing and Models of Arithmetic
• A new look at the interpolation problem
• The relative efficiency of propositional proof systems
• Forcing on bounded arithmetic II
• Forcing in Finite Structures
• Short proofs are narrow—resolution made simple
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Forcing in Proof Theory
• Generic expansions of structures
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• The Complexity of Propositional Proofs
• Fifty years of the spectrum problem: survey and new results
• Computer Science Logic
• Some applications of the notions of forcing and generic sets
• The Impact of Paul Erdős on Set Theory
• The Complexity of Propositional Proofs
• A proof of the independence of the continuum hypothesis

This page was built for publication: Partially definable forcing and bounded arithmetic