Arnold Beckmann, Samuel R Buss
ACM TOCL 2017, 18(2): 11:1-11:19
Publication year: 2017

We study consistency search problems for Frege and extended Frege proofs, namely the NP search problems of finding syntactic errors in Frege and extended Frege proofs of contradictions. The input is a polynomial time function, or an oracle, describing a proof of a contradiction; the output is the location of a syntactic error in the proof. The consistency search problems for Frege and extended Frege systems are shown to be many-one complete for the provably total NP search problems of the second order bounded arithmetic theories U^1_2 and V^1_2 , respectively.

Leave a Reply

Your email address will not be published. Required fields are marked *