Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElTanuTetel}} "Egy $L \subseteq I^$ nyelvre a következő két állítás egyenértékű: (a) $L \in NP$ .…”

2012-10-21T19:52:23Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElTanuTetel}} "Egy <math>L \subseteq I^* </math> nyelvre a következő két állítás egyenértékű: * (a) <math> L \in NP </math> .…”

Új lap

{{GlobalTemplate|Infoalap|AlgElTanuTetel}}

"Egy <math>L \subseteq I^* </math> nyelvre a következő két állítás egyenértékű:

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

Az y szót szokás még az <math>X \in L </math> á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 <math>G \in 3-SZIN</math>, akkor van (G, színezés) alakú pár L1-ben. Ha G nem <math>\in 3-SZIN</math> , 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|SzaMa]] - 2005.09.16.
-- [[AdamO|adamo]] - 2005.09.17.

[[Category:Infoalap]]

Tanú tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElTanuTetel}} "Egy L \subseteq I^* nyelvre a következő két állítás egyenértékű: * (a) L \in NP .…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElTanuTetel}} "Egy $L \subseteq I^$ nyelvre a következő két állítás egyenértékű: (a) $L \in NP$ .…”