A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

作者：Beyersdorff Olaf^*; Mueller Sebastian

来源：ACM Transactions on Computational Logic, 2010, 11(4): 22.

DOI：10.1145/1805950.1805952

• Theory
• Karp-Lipton theorem
• advice
• optimal propositional proof systems
• bounded arithmetic
• extended Frege

Cook and Krajicek have recently obtained the following Karp-Lipton collapse result in bounded arithmetic: if the theory PV proves NP subset of P/poly, then the polynomial hierarchy collapses to the Boolean hierarchy, and this collapse is provable in PV. Here we show the converse implication, thus answering an open question posed by Cook and Krajicek. We obtain this result by formalizing in PV a hard/easy argument of Buhrman et al. [2003].
In addition, we continue the investigation of propositional proof systems using advice, initiated by Cook and Krajicek. In particular, we obtain several optimality results for proof systems using advice. We further show that these optimal systems are equivalent to natural extensions of Frege systems.

• 出版日期2010-7