Une modification du système de preuve de Krom pourrait-elle être utilisée pour résoudre 3-SAT en temps polynomial?

Question

Un littéral est un entier non nul, et nous définissons $ sim x = -x $.
Une clause est un ensemble non vide de littéraux.
Un CNF est un ensemble de clauses.
Une K-Rule est une paire $ (f, c) $ où $ f $ est un CNF et $ C $ est une clause.
Un système d'épreuve de style krom (KPS) est un ensemble de k-rules.
Si $ s $ est un KPS, alors un $ s $ -poolin de $ c $ de $ f $, ou un $ (s, f) $ - preuve de $ c $, est une séquence $ langle c_1, .. , C_n Hangle $ de clauses telles que $ c = c_n $ et pour tout $ $ le i le n $, soit $ c_i in f $, soit il y a un k-rule $ r = (g, a) in S $ et une fonction $ f: {x, sim x: x in b in g lor x in a } rightarrow mathbb {z} _ { ne 0} $ qui respecte la négation telle que Laissant $ g (b): = {f (a): a ∈ B } $, nous avons $ c_i = g (a) $, et pour tout $ b in g $, il existe un $ j <i $ avec $ c_j = g (b) $.
Pour Fixed $ s $, la langue $ {(f, c): f vdash_s c } $ est décideable en temps polynomial:

read inputs F and C
if C ∈ F
    return true
let D = {x1,~x1,..,xn,~xn} be the set of literals occuring in F or C, and their negations
Contin := true
while Contin
    Contin ← false
    for (G,A) in S
        for h : {abs(x) : x ∈ B ∈ G ∨ x ∈ A} -> D # there are |D|^c such functions
            f(x) := (x > 0 ? h(x) : -h(-x))
            g(B) := {f(a) : a ∈ B}
            for B in G
                if g(B) ∉ G 
                    continue in the for-loop where h is chosen
            if g(A) ∉ F
                push g(A) to F
                Contin ← true
if C ∈ F
    return true
else
    return false

$ S $ est solide si pour tous les $ f $ et clauses de CNF $ C $, l'existence d'un $ (s, f) $ - preuve de $ c $ implique que $ f vdash c $.
$ S $ est complet pour une classe $ gamma $ de cnf si pour tout $ f in gamma $ et $ c $, si $ f vdash c $ alors $ c $ est $ (s, f) $ - prouvable .
Aucun KPS n'est complet pour Full $ SAT $, car toute clause du formulaire $ {- 1,1,2,3, .., n } $ est tautologique, mais pour tout système $ s $, $ sup { | A | : ( videset, a) in s } $ est uniquement fini, ce qui rend la clause $ (s, videset) $ - improvable pour un $ n $.
$ {( { {1 }, {- 1 } }, # vdash b $.
$ {( videset, {1, -1 }), ( { {1 } }, {1,2 }), ( { {1,2 }, { -1,3 } }, {2,3 }) } $ est complet pour $ 2 $ - $ sat $, et représente le système composé des règles (1) $ vdash a lor sim a $, (2) $ a lor a vdash a lor b $, et (3) $ a lor b, sim a lor c vdash b lor c $.
Question 1. Est-il connu qu'aucun KPS ne peut être complet pour 3 $ - $ SAT $?
Si un tel KPS était trouvé, il impliquerait $ p = np $ et la liaison polynomiale des systèmes de preuve propositionnels naturels.
Je suis particulièrement intéressé par l'exhaustivité du système $ s_3 = {( videset, {1, -1,2 }), ( { {1,2,3 }, {1,2, 4 }, {- 3, -4,5 } }, {1,2,5 }) } $ pour $ 3 $ - $ sat $, où la règle principale correspond au fait que si $ a land b rightarrow c $, $ a land b rightarrow d $, et $ c land d rightarrow e $, puis $ a land b rightarrow e $.
Question 2. Est-ce que $ S_3 $ peut être complet pour 3 $ - $ SAT $, ou au moins une classe restreinte de celle-ci telle que $ Horn $ - $ SAT CAP 3 $ - $ CNF $ ou le principe de pigeon?
Un $ (s, f, d) $ - la preuve est la même qu'un $ (s, f) $ - preuve $ langle c_1, .., c_n hangle $, sauf que nous avons une fonction $ h: { 1, .., n } rightarrow {0, .., d } $, et la dernière partie de l'ancienne définition, à savoir "$ c_j = g (b) $", est renforcé en exigeant en outre que $ H (j) <H (i) $.
Jusqu'à présent, j'ai pu montrer que si $ langle c_1, .., c_n, c_ {n + 1} rangle $ est un $ (s_3, f cup { {a, b, c } }) $ - preuve de $ c_ {n + 1} = {d, e, f } $ avec $ c_1, .., c_n in f $, puis pour $ x = a, b, c $ là-bas Existe un $ (s_3, f cup { { sim d }, { sim e }, { sim f } }, 5) $ - preuve $ langle d_1, .., D_ {23} Hangle $ de $ { sim x } $.
Cependant, l'algorithme ci-dessus prend $ o (n ^ 8) $ étapes sur le modèle de calcul RAM dans le cas de $ S_3 $. L'algorithme d'origine de Krom pour 2-SAT avait un temps d'exécution de $ o (n ^ 3) $, mais cette limite supérieure a depuis été améliorée à $ o (n) $, même si nous voulons trouver une mission satisfaisante quand on existe.
Question 3. À quelle rapidité pouvons-nous résoudre le problème de provisionnement $ S_3 $? Si ce système est complet pour 3 $ - $ SAT $, à quelle vitesse pouvons-nous trouver des affectations satisfaisantes à des formules cohérentes?