Komprese důkazu rozlišení rozdělením - Resolution proof compression by splitting

v matematická logika, důkaz komprese rozdělením je algoritmus který funguje jako postproces na rozlišení důkazy. Navrhl to Scott Cotton ve svém příspěvku „Dvě techniky pro minimalizaci rozlišení“.^[1]

Algoritmus rozdělení je založen na následujícím pozorování:

Dostal důkaz o neuspokojivosti ${ displaystyle pi}$ a proměnná ${ displaystyle x}$, je snadné znovu uspořádat (rozdělit) důkaz v důkazu o ${ displaystyle x}$ a doklad o ${ displaystyle neg x}$ a rekombinace těchto dvou důkazů (o další krok řešení) může mít za následek menší důkaz než originál.

Všimněte si, že použití rozdělení v důkazu ${ displaystyle pi}$ pomocí proměnné ${ displaystyle x}$ nezruší platnost druhé aplikace algoritmu pomocí proměnné differente ${ displaystyle y}$. Vlastně metoda navržená bavlnou^[1] generuje posloupnost důkazů ${ displaystyle pi _ {1} pi _ {2} ldots}$, kde každý důkaz ${ displaystyle pi _ {i + 1}}$ je výsledkem použití rozdělení na ${ displaystyle pi _ {i}}$. Během konstrukce sekvence, pokud je důkaz ${ displaystyle pi _ {j}}$ je příliš velký, ${ displaystyle pi _ {j + 1}}$ je nastaven jako nejmenší důkaz v ${ displaystyle { pi _ {1}, pi _ {2}, ldots, pi _ {j} }}$.

Pro dosažení lepšího poměru komprese a času je žádoucí heuristika pro výběr proměnné. Z tohoto důvodu, bavlna^[1] definuje "aditivitu" kroku řešení (s předchůdci) ${ displaystyle p}$ a ${ displaystyle n}$ a resolvent ${ displaystyle r}$):

${ displaystyle operatorname {add} (r): = max (| r | - max (| p |, | n |), 0)}$

Potom pro každou proměnnou ${ displaystyle v}$se vypočítá skóre sečtením aditivity všech kroků rozlišení v ${ displaystyle pi}$ s otočným čepem ${ displaystyle v}$ spolu s počtem těchto kroků řešení. Označme každé takto vypočítané skóre pomocí ${ displaystyle add (v, pi)}$, každá proměnná je vybrána s pravděpodobností úměrnou jejímu skóre:

${ displaystyle p (v) = { frac { operatorname {add} (v, pi _ {i})} { sum _ {x} { operatorname {add} (x, pi _ {i} )}}}}$

Rozdělit důkaz o neuspokojivosti ${ displaystyle pi}$ v důkazu ${ displaystyle pi _ {x}}$ z ${ displaystyle x}$ a důkaz ${ displaystyle pi _ { neg x}}$ z ${ displaystyle neg x}$, Bavlna ^[1] navrhuje následující:

Nechat ${ displaystyle l}$ označuje doslovný a ${ displaystyle p oplus _ {x} n}$ označují řešení klauzulí ${ displaystyle p}$ a ${ displaystyle n}$ kde ${ displaystyle x in p}$ a ${ displaystyle neg x v n}$. Poté definujte mapu ${ displaystyle pi _ {l}}$ na uzlech v rozlišení ${ displaystyle pi}$:

${ displaystyle pi _ {l} (c): = { begin {cases} c, & { text {if}} c { text {je vstup}} pi _ {l} (p ), & { text {if}} c = p oplus _ {x} n { text {and}} (l = x { text {or}} x notin pi _ {l} (p) ) pi _ {l} (n), & { text {if}} c = p oplus _ {x} n { text {and}} (l = neg x { mbox {or} } neg x notin pi _ {l} (n)) pi _ {l} (p) oplus _ {x} pi _ {l} (p), & { text {if} } x in pi _ {l} (p) { text {and}} neg x in pi _ {l} (n) end {cases}}}$

Také nechte ${ displaystyle o}$ být prázdná klauzule v ${ displaystyle pi}$. Pak, ${ displaystyle pi _ {x}}$ a ${ displaystyle pi _ { neg x}}$ jsou získány výpočtem ${ displaystyle pi _ {x} (o)}$ a ${ displaystyle pi _ { neg x} (o)}$, resp.

Poznámky