Switch to: References

Add citations

You must login to add citations.
  1. Towards NP – P Via Proof Complexity and Search.Samuel R. Buss - 2012 - Annals of Pure and Applied Logic 163 (7):906-917.
  • On the Proof Complexity of the Nisan–Wigderson Generator Based on a Hard Np ∩ Conp Function.Jan Krajíček - 2011 - Journal of Mathematical Logic 11 (1):11-27.
    Let g be a map defined as the Nisan–Wigderson generator but based on an NP ∩ coNP -function f. Any string b outside the range of g determines a propositional tautology τb expressing this fact. Razborov [27] has conjectured that if f is hard on average for P/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. We consider a more general Statement that the tautologies have no polynomial size proofs in any propositional proof system. (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • On the Correspondence Between Arithmetic Theories and Propositional Proof Systems - a Survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
    The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11].Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krajíček and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations