A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

摘要

Cook and Krajicek [9] have obtained the following Karp-Lipton result in bounded arithmetic: if the theory PV proves NP is contained in P/poly, then PH collapses to BH, and this collapse is provable in PV. Here we show the converse implication, thus answering an open question from [9]. We obtain this result by formalizing in PV a, hard/easy argument of Buhrman, Chang, and Fortnow [3]. In addition, we continue the investigation of propositional proof systems using advice, initiated by Cook and Krajicek [9]. In particular, we obtain several optimal and even p-optimal proof systems using advice. We further show that these p-optimal systems are equivalent to natural extensions of Frege systems.