Boolen kaavojen tyydyttävyysongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15.6.2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Boolen kaavojen ( SAT , vyp ) tyydyttävyysongelma on laskennallisen monimutkaisuuden teorialle tärkeä algoritminen ongelma .

Tehtäväilmentymä on Boolen kaava , joka koostuu vain muuttujien nimistä, suluista ja operaatioista ( AND ), ( OR ) ja ( HE ). Ongelmana on: onko mahdollista antaa vääriä ja tosi arvoja kaikille kaavassa esiintyville muuttujille niin, että kaavasta tulee tosi. $\kiila$ $\vee$ $\neg$

Stephen Cookin vuonna 1971 todistaman Cookin lauseen mukaan konjunktiiviseen normaalimuotoon kirjoitettujen Boolen kaavojen SAT-ongelma on NP-täydellinen . Konjunktiivimuodossa kirjoittamisen vaatimus on olennainen, sillä esimerkiksi disjunktiivisessa normaalimuodossa esitettyjen kaavojen SAT-ongelma ratkeaa triviaalisti lineaarisessa ajassa riippuen kaavatietueen koosta (jotta kaava olisi tyydyttävä, vain läsnäolo vaaditaan vähintään yksi konjunktio , joka ei sisällä samanaikaisesti ja negatiivista jollekin muuttujalle ). $x$ ${\näyttötyyli \neg x}$ $x$

Tarkka sanamuoto

Tunnistusongelman täsmällisen muotoilemiseksi kiinnitetään äärellinen aakkoset, joiden avulla määritellään kieliinstanssit. Hopcroft , Motwani ja Ullman kirjassaan Introduction to Automata Theory , Languages, and Computation ehdottavat seuraavan aakkoston käyttöä : . ${\displaystyle \{\wedge ,\vee ,\neg ,(,),x,0,1\))$

Tätä aakkosta käytettäessä sulut ja operaattorit kirjoitetaan luonnollisesti, ja muuttujat saavat seuraavat nimet: , numeroidensa mukaan binäärimuodossa . ${\näyttötyyli x1,x10,x11,x100,\pisteet }$

Olkoon jollain boolen kaavalla , joka on kirjoitettu tavallisella matemaattisella merkinnällä, merkkien pituus. Siinä kunkin muuttujan jokaista esiintymistä kuvattiin vähintään yhdellä symbolilla, joten tässä kaavassa ei ole enempää kuin muuttujia. Tämä tarkoittaa, että yllä ehdotetussa merkinnässä jokainen muuttuja kirjoitetaan symboleilla. Tässä tapauksessa koko kaava uudessa merkinnässä on merkkien pituinen, eli merkkijonon pituus kasvaa polynomimäärän kertoja. $N$ $N$ $O\left(\log{N}\right)$ $O\left(N\log{N}\right)$

Esimerkiksi kaava saa muotoa . $a\wedge\neg(b\vee c)$ $x1\kiila\neg(x10\vee x11)$

Laskennallinen monimutkaisuus

Stephen Cookin vuonna 1970 julkaisemassa artikkelissa termi " NP-täydellinen ongelma " esiteltiin ensimmäisen kerran , ja SAT-ongelma oli ensimmäinen ongelma, jolle tämä ominaisuus todistettiin.

Cookin lauseen todistuksessa jokainen luokan NP tehtävä pelkistetään eksplisiittisesti SAT:ksi. Cookin tulosten ilmestymisen jälkeen NP-täydellisyys todettiin moniin muihin ongelmiin. Tässä tapauksessa useimmiten tietyn tehtävän NP-täydellisyyden todistamiseksi annetaan SAT-tehtävän polynomipelkistys annettuun ongelmaan, mahdollisesti useassa vaiheessa, eli useaa välitehtävää käyttäen.

SAT-ongelman erikoistapaukset

Mielenkiintoisia tärkeitä erityistapauksia SAT-ongelmasta ovat:

Boolen kaavojen tyydyttävyysongelma konjunktiivisessa normaalimuodossa (SATCNF tai VKNF) on samanlainen ongelma, ja kaavalle on asetettu ehto: se on kirjoitettava konjunktiivisessa normaalimuodossa ; myös NP-täydellinen ;
tyydyttävyysongelma Boolen kaavoille k-konjunktiivisessa normaalimuodossa (k-SAT tai k-SAT) - tyydyttävyysongelma, jos kaava kirjoitetaan k-konjunktiiviseen normaalimuotoon ; tämä ongelma on NP-täydellinen kohteelle . Ongelman ratkaisemiseksi voit käyttää todennäköisyyspohjaista Schoening-algoritmia ; $k\geq 3$
Boolen kaavojen tyydyttävyysongelmalla 2-konjunktiivisessa normaalimuodossa on polynomiratkaisu, eli se kuuluu luokkaan P .

CDCL-ratkaisijat

Yksi tehokkaimmista SAT-tehtävien rinnakkaismenetelmistä on CDCL-ratkaisijat (CDCL, englantilainen konfliktilähtöinen lauseoppiminen ), jotka perustuvat DPLL-algoritmin ei-kronologisiin muunnelmiin [1] [2] .

Katso myös

Muistiinpanot

↑ Marques-Silva JP GRASP: Hakualgoritmi ehdotuksen tyydyttävyyttä varten / JP Marques-Silva, KA Sakallah // IEEE Transactions on Computers. - 1999. - Voi. 48, nro 5. - P. 506-521.
↑ Semenov A. A., Zaikin O. S. Algoritmit hajotusjoukkojen rakentamiseen SAT-ongelmien suurten lohkojen rinnastukseen. Sarja "Mathematics" 2012. V. 5, No. 4. S. 79-94

Linkit

Kansainvälisten SAT-kilpailujen verkkosivu
Sat Live on yleinen SAT-sivusto.

NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma	Pakkaus säiliöihin kaksiulotteinen pakkaus lineaarinen pakkaus pakkaus painon mukaan pakkaus arvon mukaan Reppu ongelma
graafiteorian joukkoteoria	Vertex-kannen ongelma Napsauta ongelma Itsenäisen joukon (joukon) ongelma Aseta peittoongelma Steinerin ongelma Matkamyyjän ongelma Yleinen matkamyyjän ongelma
Algoritmiset ongelmat	Boolen kaavojen tyydyttävyysongelma (konjunktiivisessa normaalimuodossa)
Logiikkapelejä ja pulmia	Yleiset tunnisteet (peli N 2 -1:ssä) lyhin ratkaisu ongelma Ongelmat, joiden ratkaisuja käytetään Tetrisissä Yleistynyt Sudoku-ongelma Latinalaisen neliön täyttöongelma Kakuron tehtävä
Vaikeusluokat Toimintatutkimus Optimointi Kombinatorinen optimointi Sovellettu matematiikka Algoritmien teoria Dynaaminen ohjelmointi 21 NP-täydellinen Karp-ongelma