Simulating non-prenex cuts in quantified propositional calculus

0364309 - MÚ 2012 RIV DE eng J - Journal Article
Jeřábek, Emil - Nguyen, P.
Simulating non-prenex cuts in quantified propositional calculus.
Mathematical Logic Quarterly. Roč. 57, č. 5 (2011), s. 524-532. ISSN 0942-5616. E-ISSN 1521-3870
R&D Projects: GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : proof complexity * prenex cuts * quantified propositional calculus
Subject RIV: BA - General Mathematics
Impact factor: 0.496, year: 2011
http://onlinelibrary.wiley.com/doi/10.1002/malq.201020093/abstract

We show that the quantified propositional proof systems G_i are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Sigma^q_i (or prenex Pi^q_i). Previously this was known only for the treelike systems G^*_i.
Permanent Link: http://hdl.handle.net/11104/0199828