Schoeningin algoritmi

Schöningin algoritmi on Uwe Schöningin vuonna 1999 ehdottama todennäköisyysalgoritmi Boolen kaavojen tyydyttävyysongelman ratkaisemiseksi k - konjunktiivisessa normaalimuodossa .

Kuvaus 3-SAT-ratkaisulle

Sinulle annetaan Boolen kaava 3-konjunktiivisessa normaalimuodossa . $F(x_{1},x_{2},\dots ,x_{n})$
Toista kerran: $\lceil 20\cdot {\sqrt {3\cdot \pi \cdot n))\cdot ({\frac {4}{3)))^{n}\rceil$
1. Aseta satunnaisesti joukko muuttujia . ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{n})\in \{0,1\}^{n))$
2. Jos looginen kaava on tosi, tulosta ja poistu. $F(\alpha )$ $\alpha$
3. Toista kerran: $3\cdot n$
  1. Valitse disjunktio , joka ei tyydytä . $c_{i}$ $\alpha$
  2. Valitse muuttuja . $x_{j}$ $c_{i}$
  3. Asenna . $\alpha =(\alpha _{1},\alpha _{2},\dots ,{\overline {\alpha _{j))},\dots ,\alpha _{n})$
  4. Jos looginen kaava on tosi, tulosta ja poistu. $F(\alpha )$ $\alpha$
Tulostus " mahdoton". $F$

Aika monimutkaisuus

Schoeningin algoritmilla on aikamonimutkaisuus , jossa on muuttujien määrä ja disjunktioiden määrä, edellyttäen, että Boolen kaavan tyydyttävyys tarkistetaan . Jos Boolen kaava ei ole mahdollinen, niin Schoeningin algoritmi palauttaa aina oikean tuloksen. $O(m\cdot n^{3/2}\cdot (4/3)^{n})=O(m\cdot 1,334^{n})$ $n$ $m$ $O(3m)$ $F$

Virhearvio

Jos Boolen kaava on tyydyttävä, virhetodennäköisyys on aina pienempi . Todistuksessa merkitään muuttujien joukko, jolle on tosi, ja myös todennäköisyys, että algoritmi löytää sisäkkäisestä silmukasta (tätä vaihetta kutsutaan myös paikalliseksi hauksi). Siten on alaraja todennäköisyydelle löytää tyydyttävä muuttujajoukko paikallishaun avulla. Seuraavaksi näytämme sen . Kahden joukon välinen etäisyys on niissä olevien erillisten bittien lukumäärä. Määritelkäämme luokka joukoksi kokoelmia, jotka poikkeavat hieman joukosta , ts. . Siten kaikki sarjat voidaan jakaa luokkiin. Reilun vuoksi . Todennäköisyys valita elementti satunnaisesti joukosta on . Paikallisessa haussa huomioidaan disjunktio , jota generoitu muuttujajoukko ei tyydytä, ja jos joukko valitaan satunnaisesti uudelleen, todennäköisyys löytää tyydyttävä muuttuja on yhtä suuri kuin . Näin ollen todennäköisyys siirtyä luokasta luokkaan on vähintään . Todennäköisyys päästä luokasta luokkaan on yhtä suuri kuin maksimi . Olkoon todennäköisyys päästä luokasta portaittain luokkaan , ts. löytää ratkaisu . Tässä tapauksessa missä on mahdollisten siirtymien määrä suuntaan ja todennäköisyys päästä ulos luokasta on . Kun kaavat on korvattu toisillaan ja laskettu likimääräisesti tulos, saadaan todennäköisyys sille, että paikallishaun aikana ei löydy tyydyttävää muuttujajoukkoa, joka on yhtä suuri kuin , ja tällaisten hakujen jälkeen todennäköisyys on jo yhtä suuri kuin . $F$ $5\cdot 10^{-5}$ $\alpha ^{*}$ $F(\alpha ^{*})$ ${\displaystyle p_{l))$ $\alpha ^{*}$ ${\displaystyle p_{l))$ $p_{l}\leqslant {\frac {1}{20\cdot {\sqrt {3\cdot \pi \cdot n))))\cdot \left({\frac {3}{4)) \oikea)^{n}$ $\alpha$ $\beeta$ $C(j)$ $\alpha ^{*}$ $j$ ${\displaystyle C(j)=\{\beta \in \{0,1\}^{n}\mid \operaattorinimi {dist} (\alpha ^{*},\beta )=j\))$ $n+1$ $j\in \{0,1,\dots ,n\}$ $|C(j)|={\tbinom {n}{j))$ $C(j)$ $p_{j}={\tbinom {n}{j}}\cdot 2^{-n}$ $c_{i}$ $1/3$ $C(j)$ $C(j-1)$ $1/3$ $C(j)$ $C(j+1)$ $2/3$ ${\näyttötyyli q_{j,i))$ $C(j)$ $j+2i$ $C(0)$ $\alpha ^{*}$ $q_{i,j}={\binom {j+2i}{i}}\cdot {\frac {j}{j+2i}}\cdot \left({\frac {1}{3} }\oikea)^{j+1}\cdot \left({\frac {2}{3}}\right)^{i}$ ${\binom {j+2i}{i}}\cdot {\frac {j}{j+2i}}$ $\alpha ^{*}$ $\alpha ^{*}$ $C(j)$ ${\displaystyle q_{j}=\sum _{i=0}^{j}q_{j,i))$ ${\tilde {p}}=1-{\frac {1}{2\cdot {\sqrt {3\pi n}}}}\cdot \left({\frac {3}{4}} \oikea)^{n}$ $t$ $(1-{\tilde {p)))^{\lceil 20\cdot {\sqrt {3\cdot \pi \cdot n))\cdot ({\frac {4}{3)))^ {n}\rceil }\leqslant e^{-10}\leqslant 5\cdot 10^{-5}$

Muistiinpanot

↑ T. Schoning. Todennäköisyyspohjainen algoritmi k-SAT:lle ja rajoitteiden tyytyväisyysongelmille // 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). — New York City, NY, USA: IEEE Comput. Soc, 1999, s. 410-414 . — ISBN 978-0-7695-0409-4 . - doi : 10.1109/SFCS.1999.814612 .