Cook-Levin-tétel

1. Sablon:Label

Cook–Levin-tétel

A Cook–Levin-tétel a számítástudomány egyik legfontosabb eredménye, amely megmutatja, hogy az NP osztály problémái között léteznek különösen nehéz problémák, amelyeket NP-teljes problémáknak nevezünk.

---

1. A tétel állítása

A Cook–Levin-tétel szerint a Boole-függvények kielégíthetőségi problémája (SAT, azaz Satisfiability Problem) NP-teljes:

• SAT probléma: Döntsd el, hogy egy adott Boole-kifejezés kielégíthető-e, azaz létezik-e olyan értékadás a változókra (igaz/hamis), amely a kifejezést igazra értékeli.

---

2. Mi az NP-teljesség?

1. NP (nem-determinisztikus polinomiális idő):

 * Az NP osztályba tartozó problémák olyanok, amelyek megoldásait polinomiális idő alatt ellenőrizni lehet egy determinisztikus Turing-géppel.

1. NP-teljes problémák:

 * Egy probléma NP-teljes, ha:
   # Maga is az NP osztályba tartozik.
   # Minden más NP-probléma polinomiális idő alatt redukálható rá (azaz megoldható az ő megoldása segítségével).

---

3. A Cook–Levin-tétel jelentősége

1. Az első NP-teljes probléma:

 * A Cook–Levin-tétel kimondja, hogy a SAT probléma az első ismert NP-teljes probléma.

1. Redukciós módszer alapja:

 * Mivel minden NP-probléma redukálható SAT-ra, ha bármikor találnánk egy polinomiális idejű algoritmust SAT megoldására, az minden NP-problémára is megoldást nyújtana.

1. P vs NP kérdés:

 * A Cook–Levin-tétel az alapja annak a híres nyitott kérdésnek, hogy $P=NP$-e. Ha SAT polinomiális idő alatt megoldható lenne, az bizonyítaná, hogy $P=NP$.

---

4. Cook–Levin-tétel bizonyítása (áttekintés)

Cél

Bizonyítani, hogy bármely NP-probléma polinomiális idő alatt átalakítható SAT-ra.

Lépések

1. Turing-gép modellezése:

 * Minden NP-probléma megoldható egy nem-determinisztikus Turing-géppel.
 * Egy Turing-gép működése rögzíthető: szalagállapotok, fejek pozíciója és az átmeneti függvények.

1. Turing-gép futásának rögzítése:

 * A Turing-gép működését egy Boole-kifejezéssel reprezentáljuk.
 * A változók az egyes szalagcellák, a gép állapota és a fej pozíciója.

1. Kielégíthetőségi probléma megalkotása:

 * A Boole-kifejezés azt írja le, hogy létezik-e olyan bemenet, amely kielégíti a Turing-gép működésének szabályait.
 * Ha a Boole-kifejezés kielégíthető, az azt jelenti, hogy a Turing-gép elfogad egy adott bemenetet.

1. Redukció:

 * Megmutatja, hogy egy tetszőleges NP-probléma megoldása SAT-ra redukálható polinomiális időben.

---

5. Példa a SAT problémára

Kifejezés

$(x_1\vee \mathrm{\neg }{x}_2)\wedge (\mathrm{\neg }{x}_1\vee x_3)$

Kérdés

• Létezik-e olyan értékadás ($x_1,x_2,x_3$), amely a kifejezést igazra értékeli?

Megoldás

• Próbáljuk ki az összes lehetőséget ($2^n$, ahol $n$ a változók száma):

 * $x_1=\text{True},x_2=\text{False},x_3=\text{True}$ kielégíti a kifejezést.

---

6. Algoritmikus megközelítés

A SAT megoldására több algoritmus létezik:

1. Brute-force (exponenciális idő):

 * Próbáld ki az összes lehetséges értékadást.

1. DPLL algoritmus:

 * Egy rekurzív backtracking-alapú algoritmus, amely hatékonyabb, mint a brute-force.

1. Modern SAT-solverek:

 * Például CDCL (Conflict-Driven Clause Learning), amelyet ipari alkalmazásokban is használnak.

---

7. Következmények

1. P vs NP kérdés:

 * A Cook–Levin-tétel alapvető fontosságú a $P=NP$ kérdés szempontjából.
 * Ha valaha találnánk egy polinomiális idejű algoritmust SAT-ra, akkor $P=NP$.

1. Gyakorlati alkalmazások:

 * SAT-solvereket széles körben használják ipari alkalmazásokban, például hardvertervezésben és automatikus hibakeresésben.

---

8. Összefoglalás

A Cook–Levin-tétel megmutatja, hogy a SAT probléma az első NP-teljes probléma, és ezzel lefektette az NP-teljesség elméleti alapjait. Ez az eredmény alapvető a számítástudomány számára, mert megmutatja, hogy bizonyos problémák megoldása rendkívüli nehézségekkel járhat.

Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T