We study the complexity of proof systems augmenting resolution with inference rules that allow, given a formula $\Gamma$ in conjunctive normal form, deriving clauses that are not necessarily logically implied by $\Gamma$ but whose addition to $\Gamma$ preserves satisfiability. When the derived clauses are allowed to introduce variables not occurring in $\Gamma$, the systems we consider become equivalent to extended resolution. We are concerned with the versions of these systems without new variables. They are called BC${}^-$, RAT${}^-$, SBC${}^-$, and GER${}^-$, denoting respectively blocked clauses, resolution asymmetric tautologies, set-blocked clauses, and generalized extended resolution. Each of these systems formalizes some restricted version of the ability to make assumptions that hold "without loss of generality," which is commonly used informally to simplify or shorten proofs. Except for SBC${}^-$, these systems are known to be exponentially weaker than extended resolution. They are, however, all equivalent to it under a relaxed notion of simulation that allows the translation of the formula along with the proof when moving between proof systems. By taking advantage of this fact, we construct formulas that separate RAT${}^-$ from GER${}^-$ and vice versa. With the same strategy, we also separate SBC${}^-$ from RAT${}^-$. Additionally, we give polynomial-size SBC${}^-$ proofs of the pigeonhole principle, which separates SBC${}^-$ from GER${}^-$ by a previously known lower bound. These results also separate the three systems from BC${}^-$ since they all simulate it. We thus give an almost complete picture of their relative strengths.
翻译:我们研究证明系统的复杂性,以推断规则来增加分辨率,这种规则允许,考虑到公式$=Gamma美元,以正统形式计算,得出一些不一定逻辑上由Gamma美元暗含的条款,但用Gamma美元补充美元则保留了相对性。当允许衍生条款引入不发生于$\Gamma美元的变量时,我们认为这些系统就等同于延伸分辨率。我们对这些系统没有新变量的版本感到关切。这些系统称为BC$-美元、RAT$-美元、SBB$-GER$和GER$_GER$-美元,指出条款几乎被封锁,解决了不对称的调值、固定条款和普遍扩大的分辨率。这些系统都正式确定了某些限制性的假设版本,即“在不丢失一般性的情况下”,通常用来简化或缩短证据。除SBC$_美元外,这些系统已知比扩展的分辨率快得多。然而,这些系统都相当于一个较宽松的模拟概念,让我们能够翻译公式的相对值-美元、不对称的调值、设置了SAT原则,因此,在不同的系统之间也形成了一个不同的证明。