An oracle separating conjectures about incompleteness in the finite domain Abstract   Pudlak  19  lists several major complexity theoretic conjectures relevant to proof complexity and asks for oracles that separate pairs of corresponding relativized conjectures. Among these conjectures are:  xe2x80xa2      DisjNP   : The class of all disjoint NPpairs does not have manyone complete problems.   xe2x80xa2      SAT   : NP does not contain manyone complete sets that have Poptimal proof systems.   xe2x80xa2      UP   : UP does not have manyone complete problems.   xe2x80xa2       NP   xe2x88xa9   coNP    :     NP   xe2x88xa9   coNP     does not have manyone complete problems.     As one answer to this question, we construct an oracle relative to which (among others)    DisjNP   ,    xc2xac   SAT    ,    UP   , and     NP   xe2x88xa9   coNP     hold. Hence, there is no relativizable proof for the implication     DisjNP   xe2x88xa7   UP   xe2x88xa7   NP   xe2x88xa9   coNP   xe2x87x92   SAT    . In particular, regarding the conjectures by Pudlak this extends a result by Khaniki  11 .

Resolution Lower Bounds for Refutation Statements For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolution refutations of a propositional statement that the formula has a resolution refutation. We describe three applications. (1) An open question in (Atserias, Muller 2019) asks whether a certain natural propositional encoding of the above statement is hard for Resolution. We answer by giving an exponential size lower bound. (2) We show exponential resolution size lower bounds for reflection principles, thereby improving a result in (Atserias, Bonet 2004). (3) We provide new examples of CNFs that exponentially separate Res(2) from Resolution (an exponential separation of these two proof systems was originally proved in (Segerlind, Buss, Impagliazzo 2004)).