Tanú tétel

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

"Egy $L\subseteq I^{*}$ nyelvre a következő két állítás egyenértékű:

• (a) $L\in NP$ .
• (b) Van olyan c > 0 állandó továbbá egy $L_{1}\in P$ nyelv, mely olyan $(x,y)\in (I^{*})^{2}$ párokból áll, hogy $|y|\leq |x|^{c}$ és $x\in I^{*}$ esetén $x\in L$ pontosan akkor, ha van $y\in I^{*}$ úgy, hogy $(x,y)\in L_{1}$ .

Az y szót szokás még az $X\in L$ állítás tanújának, vagy az x elfogadásához vezető sejtésnek is neveni. A súgás és sejtés szavakból kiszüremlő bizonytalanság arra hivatott utalni, hogy az y-nal szemben nincs kiszámíthatósági követelmény."

Tehát tanúnak nevezünk egy jelsorozatot, aki segít nekünk bebizonyítani egy szóról, hogy az adott nyelv tagja. A tanú előállítására nincsen algoritmusunk, az egyszerűen csak van. A tanú a következőképpen néz ki:

• a tanú hossza a szó hosszának polinomja (tehát nem lehet túl hosszú)
• tudunk mondani egy algoritmust, aminek a bemenete a szó és a tanú, és (det) polinom időben eldönti, hogy a szó a nyelv tagja.

Tanú tétel: ha egy nyelv minden szavához létezik tanú, akkor a nyelv NP-beli.

Pl.

• Nyelv: 3 színnel színezhető gráfok (*3-SZÍN*).
  • Tanú: Egy n szögpontú 3 színnel színezhető G gráf egy helyes 3-színezése, azaz felsoroljuk minden pont színét.
  • a tanú elég rövid: O(n)
  • a tanú gyorsan ellenőrizhető: minden élre megvizsgáljuk, hogy a két vége különböző színű-e. (ez érezhetően polinom, nem kell vacakolni a bizonyítással)
  • Teljesülnek a tanú-tétle (b) részének követelményei: ha $G\in 3-SZIN$, akkor van (G, színezés) alakú pár L1-ben. Ha G nem $\in 3-SZIN$ , akkor pedig nem létezHET ilyen pár.
  • tehát a nyelv NP-beli
  • (Az, hogy honnan szedjük a tanút, nem érdekes. Ha tudnánk rá gyors algoritmust, akkor magát a problémát is gyorsan meg tudnánk oldani)

-- SzaMa - 2005.09.16. -- adamo - 2005.09.17.