È possibile utilizzare una modifica del sistema di prova di KROM per risolvere 3-Sat nel tempo polinomiale?

Question

Un letterale è un numero intero diverso da zero e definiamo $ sim x = -x $.
Una clausola è un insieme non vuoto di letterali.
Un CNF è un insieme di clausole.
Un k-role è una coppia $ (f, c) $ dove $ f $ è un CNF e $ c $ è una clausola.
Un sistema di prova in stile KROM (KPS) è un insieme di k-rule.
Se $ s $ è un KPS, allora un $ s $ -of di $ c $ da $ f $, o un $ (s, f) $-prova di $ c $, è una sequenza $ langle c_1, .. , C_n rangle $ di clausole in modo tale che $ c = c_n $ e per tutti $ 1 le i le n $, $ c_i in f $ o c'è un k-rule $ r = (g, a) in S $ e una funzione $ f: {x, sim x: x in b in g lor x in a } destrorrow mathbb {z} _ { ne 0} $ che rispetta la negazione tale Lasciando $ g (b): = {f (a): a ∈ B } $, abbiamo $ c_i = g (a) $ e per tutto $ b in g $, esistono alcuni $ j <i $ con $ c_j = g (b) $.
Per fisso $ s $, la lingua $ {(f, c): f vdash_s c } $ è decidabile a tempo polinomiale:

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 $ è solido se per tutti i CNF $ f $ e clausole $ c $, l'esistenza di un $ (s, f) $-la prova di $ c $ implica che $ f vdash c $.
$ S $ è completo per una classe $ gamma $ di cnf se per tutti $ f in gamma $ e $ c $, se $ f vdash c $ allora $ c $ è $ (s, f) $-dimostrabile .
Nessun KPS è completo per $ sab $, poiché qualsiasi clausola del modulo $ {-1,1,2,3, .., n } $ è tautologica, ma per qualsiasi sistema $ s $, $ sup { | A | : ( vuoto, a) in s } $ è solo finito, rendendo la clausola $ (s, vuoto) $-non costabile per sufficientemente grande $ n $.
$ {( { {1 }, {-1 } }, {2 }) } $ è completo per $ 1 $-$ sat $ e rappresenta la regola $ a, sim a vdash b $.
$ {( vuoto, {1, -1 }), ( { {1 } }, {1,2 }), ( { {1,2 }, { -1,3 } }, {2,3 }) } $ è completo per $ 2 $-$ sat $ e rappresenta il sistema costituito dalle regole (1) $ vdash a lor sim a $, (2) $ a lor a vdash a lor b $ e (3) $ a lor b, sim a lor c vdash b lor c $.
Domanda 1. Si sa che nessun KPS audio può essere completo per $ 3 $-$ sab $?
Se fosse stato trovato un tale KPS, implicherebbe $ p = np $ e la rilevazione polinomiale dei sistemi di prova proposizionale naturale.
Sono particolarmente interessato alla completezza del sistema $ s_3 = {( vuoto, {1, -1,2 }), ( { {1,2,3 }, {1,2, 4 }, {-3, -4,5 } }, {1,2,5 }) } $ per $ 3 $-$ sat $, dove la regola principale corrisponde al fatto che se $ A Land B Rightarrow C $, $ A Land B Rightarrow D $, e $ C Land d Rightarrow e $, quindi $ a Land B Rightarrow e $.
Domanda 2. $ S_3 $ può essere mostrato per essere completato per $ 3 $-$ sat $, o almeno una sua classe limitata come $ horn $-$ sat cap 3 $-$ cnf $ o il principio di piccione?
A $ (s, f, d) $-la prova è la stessa di un $ (s, f) $-prova $ langle c_1, .., c_n rangle $, tranne per il fatto che abbiamo una funzione $ h: { 1, .., n } destrowarrow {0, .., d } $, e l'ultima parte della vecchia definizione, vale a dire "$ c_j = g (b) $", è rafforzata richiedendo inoltre che $ H (j) <h (i) $.
Finora, sono stato in grado di mostrare che se $ langle c_1, .., c_n, c_ {n+1} rangle $ è un $ (s_3, f coppa { {a, b, c } }) $-prova di $ c_ {n+1} = {d, e, f } $ con $ c_1, .., c_n in f $, quindi per $ x = a, b, c $ lì esiste un $ (s_3, f coppa { { sim d }, { sim e }, { sim f } }, 5) $-prova $ langle d_1, .., D_ {23} rangle $ di $ { sim x } $.
Tuttavia, l'algoritmo sopra indicato prende $ O (n^8) $ passi sul modello RAM del calcolo nel caso di $ S_3 $. L'algoritmo originale di Krom per 2-Sat ha avuto un tempo di esecuzione di $ o (n^3) $, ma questo limite superiore è stato da allora migliorato a $ o (n) $, anche se vogliamo trovare un incarico soddisfacente quando si esiste.
Domanda 3. Quanto velocemente possiamo risolvere il problema di fornibilità $ s_3 $? Se questo sistema è completo per $ 3 $-$ sab $, quanto velocemente possiamo trovare incarichi soddisfacenti a formule coerenti?