Order:
  1.  16
    The limits of tractability in Resolution-based propositional proof systems.Stefan Dantchev & Barnaby Martin - 2012 - Annals of Pure and Applied Logic 163 (6):656-668.
  2.  22
    Relativization makes contradictions harder for Resolution.Stefan Dantchev & Barnaby Martin - 2014 - Annals of Pure and Applied Logic 165 (3):837-857.
    We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res, as well as their tree-like versions, Res⁎. The contradictions we use are natural combinatorial principles: the Least number principle, LNPn and an ordered variant thereof, the Induction principle, IPn.LNPn is known to be easy for Resolution. We prove that its relativization is hard for Resolution, and more generally, the relativization of LNPn iterated d times provides a separation between Res and Res. We prove the (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  3.  32
    Tree-Resolution complexity of the Weak Pigeon-Hole Principle а.Stefan Dantchev & Sren Riis - forthcoming - Complexity.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark