az első dolog, hogy megértsük, hogy P és NP osztályozza nyelvek, nem probléma. Ahhoz, hogy megértsük, mit jelent ez, először szükségünk van néhány más meghatározásra.
az ábécé egy nem üres véges szimbólumkészlet.
{01} egy ábécé, mint az ASCII karakterkészlet. {} nem ábécé, mert üres. N (egész számok) nem ábécé, mert nem véges.
legyen Σ ábécé. A Σ véges számú szimbólumának rendezett konkatenációját Σ felett szónak nevezzük.
a101 egy szó az ábécé felett {01}. Az üres szó (gyakran ε-ként írva) egy szó bármely ábécé felett. A penguin karakterlánc az ASCII karaktereket tartalmazó ábécé feletti szó. A π szám decimális jelölése nem egy szó az ábécé felett {.01234578, 9} mert nem véges.
A W szó hossza, |w| – ként írva, a benne lévő szimbólumok száma.
például |hello| = 5 és |ε| = 0. Minden w, |w| ∈ n szóra, ezért véges.
legyen Σ ábécé. A Σ＊ halmaz tartalmazza a Σ feletti összes szót, beleértve az ε-t is. A Σ + halmaz tartalmazza a Σ feletti összes szót, kivéve az ε-t. N ∈ N esetén Σn az n hosszúságú Szavak halmaza.
minden Σ, Σ＊ És Σ+ ábécé esetében végtelen megszámlálható halmazok. Az ASCII karakterkészlet ΣASCII esetén a reguláris kifejezések .* és .+ ΣASCII＊ és ΣASCII+.
{01}a 7 bites ASCII kódok halmaza {00000000000001111111101} 32 a 32 bites egész értékek halmaza.
legyen Σ ábécé és L&Subseteq; Σ＊. L-t Σ feletti nyelvnek nevezik.
egy Σ ábécé esetében az üres halmaz és Σ＊ triviális nyelvek Σ felett. Az előbbit gyakran üres nyelvnek nevezik. Az üres {} nyelv és a csak az üres {ε} szót tartalmazó nyelv különbözik.
a {01}32 részhalmaza, amely megfelel a nem NaN IEEE 754 lebegőpontos értékeknek, véges nyelv.
A nyelvek végtelen számú szóval rendelkezhetnek, de minden nyelv számolható. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789235711, 13,…} a prímszámok tizedes jelölésben való jelölése a megfelelő részhalmaza. A ?\d+\.\d*(?\d+)? reguláris kifejezésnek megfelelő összes szót tartalmazó nyelv az ASCII karakterkészlet feletti nyelv (a C programozási nyelv által meghatározott érvényes lebegőpontos kifejezések egy részhalmazát jelöli).
nincs olyan nyelv, amely minden valós számot tartalmazna (bármilyen jelölésben), mivel a valós számok halmaza nem számolható.
legyen Σ ábécé és L&Subseteq; Σ＊. A D gép úgy dönt, hogy L, ha minden W &in bemenetnél; Σ＊ véges időben kiszámítja az xL(w) karakterisztikus függvényt. A jellemző függvény meghatározása:
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.egy ilyen gépet l-nek döntőnek nevezünk.
sok gépmodell létezik. A legáltalánosabb, amely ma gyakorlati használatban van, a Turing gép modellje. A Turing gép korlátlan lineáris tároló fürtözött sejtekbe. Minden cella pontosan egy ábécé szimbólumát tudja tartani az idő bármely pontján. A Turing gép számítási lépésként végzi a számítást. Minden lépésben képes egy cellát olvasni, esetleg felülírni az értékét, majd az olvasási/írási fejet egy pozícióval balra vagy jobbra mozgatni. Milyen műveletet hajt végre a gép, egy véges állapotú automata vezérli.
egy véges utasításkészlettel és korlátlan tárhellyel rendelkező véletlen hozzáférésű gép egy másik olyan gépmodell, amely ugyanolyan erős, mint a Turing gépmodell.
ennek a beszélgetésnek a kedvéért nem fogunk zavarni minket az általunk használt pontos gépmodellel, hanem elegendő azt mondani, hogy a gépnek véges determinisztikus vezérlőegysége van, korlátlan tárolás, és számítható lépések sorozataként számít egy számítást.
mivel a kérdésében használta, feltételezem, hogy már ismeri a “big-O” jelölést, tehát itt csak egy gyors frissítő.
Let f: N → be a function. Az O(f) halmaz tartalmazza az összes G: N → N függvényt, amelyre N0 ∈ N és C ∈ N konstansok léteznek, úgy, hogy minden n ∈ N esetén n > n0 igaz, hogy g(n) ≤ c f (n).
most készek vagyunk megközelíteni a valódi kérdést.
a p osztály tartalmazza az összes l nyelvet, amelyre létezik egy D Turing gép, amely úgy dönt, hogy L, és egy állandó k ∈ N, hogy minden W bemenet esetén a D legfeljebb t(|w|) lépések után a T ∈ O(N ↦ nk) függvényhez.
mivel O(n ↦ nk) matematikailag helyes, kényelmetlen írni és olvasni, a legtöbb ember – hogy őszinte legyek, mindenki, kivéve magam – általában egyszerűen O(nk) ír.
vegye figyelembe, hogy a kötés a W hosszától függ. ezért a prímek nyelvére vonatkozó érvelés csak az unaray kódolásokban szereplő számokra helyes, ahol az n szám w kódolásához a |w| kódolás hossza arányos n-vel. senki sem használna ilyen kódolást a gyakorlatban. Egy fejlettebb algoritmus használata, mint az összes lehetséges tényező egyszerű kipróbálása, azonban megmutatható, hogy a prímszámok nyelve P-ben marad, ha a bemenetek bináris (vagy bármely más bázisra) vannak kódolva. (A hatalmas érdeklődés ellenére ezt csak Manindra Agrawal, Neeraj Kayal és Nitin Saxena tudta bizonyítani egy díjnyertes lapban 2004-ben, így sejthető, hogy az algoritmus nem túl egyszerű.)
a triviális nyelvek {} és Σ＊, valamint a nem triviális nyelv {ε} nyilvánvalóan p (bármely ábécé Σ). Tud írni funkciók a kedvenc programozási nyelv, hogy egy string bemenetként, majd vissza egy logikai megmondja, hogy a string egy szót a nyelv mindegyik, és bizonyítani, hogy a függvény polinom futási idő komplexitás?
minden reguláris nyelv (egy reguláris kifejezés által leírt nyelv) P.
legyen Σ ábécé és L &Subseteq; Σ＊. A v gép, amely két w, c Σ Σ encoded és véges számú lépés után 0 vagy 1 kimenetek kódolt tuple-jét veszi fel, az L hitelesítője, ha a következő tulajdonságokkal rendelkezik.
- Given (w, c), V kimenetek 1 csak akkor, ha w ∈ L.
- minden W ∈ L, létezik egy c ∈ Σ＊, hogy V(w, c) = 1.
a fenti meghatározás c-jét tanúnak (vagy tanúsítványnak) nevezik.
a hitelesítő hamis negatívokat adhat a rossz tanúnak, még akkor is, ha w valójában l-ben van. Az is szükséges,hogy a nyelv minden szavához legalább egy tanú legyen.
a nyelvi kompozit esetében, amely tartalmazza az összes olyan egész szám decimális kódolását, amelyek nem prímek, a tanú faktorizáció lehet. Például (659, 709)467231 COMPOSITE COMPOSITE. Könnyen ellenőrizheti, hogy egy papírlapon a tanú nélkül, bizonyítva, hogy a 467231 nem elsődleges, nehéz lenne számítógép használata nélkül.
nem mondtunk semmit arról, hogy egy megfelelő tanú megtalálható-e. Ez a nem determinisztikus rész.
az NP osztály tartalmazza az összes l nyelvet, amelyre létezik egy olyan Turing gép V, amely ellenőrzi az L-t és egy állandó k ∈ N-t, úgy, hogy minden bemenet (w, c) esetén a V legfeljebb t(|w|) lépésekre áll a T ∈ O(N ↦ nk) függvény esetében.
vegye figyelembe, hogy a fenti meghatározás azt jelenti, hogy minden W ∈ L esetében létezik egy C tanú |C| ≤ T(|w|). (A Turing-gép valószínűleg nem nézheti meg a tanú több szimbólumát.)
NP a P (miért?). Nem ismert, hogy léteznek-e olyan nyelvek, amelyek NP-ben vannak, de nem P.
az egész faktorizáció önmagában nem nyelv. Azonban tudunk építeni egy nyelvet, amely képviseli a döntés probléma társul hozzá. Ez azt jelenti, hogy egy olyan nyelv, amely tartalmazza az összes kapcsot (n, m), úgy, hogy n d tényezővel rendelkezik d ≤ m. hívjuk ezt a nyelvi tényezőt. Ha van egy algoritmus dönteni tényező, akkor lehet használni, hogy kiszámítja a teljes faktorizáció csak polinom rezsi elvégzésével rekurzív bináris keresés minden prímtényező.
könnyű megmutatni, hogy a tényező NP-ben van. A megfelelő tanú egyszerűen maga a d tényező lenne, és a hitelesítőnek csak azt kellene ellenőriznie, hogy D ≤ m és n mod d = 0. Mindezt polinom időben lehet megtenni. (Ne feledje, ismét, hogy a kódolás hossza számít, és ez logaritmikus n-ben.)
Ha meg tudja mutatni, hogy a tényező P-ben is van, akkor biztos lehet benne, hogy sok jó díjat kap. (És eltörte a mai kriptográfia jelentős részét.)
az NP minden nyelvére van egy brute-force algoritmus, amely determinisztikusan dönt. Egyszerűen kimerítő keresést végez minden tanú felett. (Vegye figyelembe, hogy a tanú maximális hosszát egy polinom határolja.) Tehát a prímek eldöntésére szolgáló algoritmusa valójában egy brute-force algoritmus volt a kompozit eldöntésére.
a végső kérdés megválaszolásához csökkentést kell bevezetnünk. A csökkentések az elméleti számítástechnika nagyon erős fogalma. Az egyik probléma csökkentése a másikra alapvetően egy probléma megoldását jelenti egy másik probléma megoldásával.
legyen Σ ábécé és B legyen a Σ feletti nyelv. A polinom-idő sok-egy redukálható B, ha létezik egy függvény f: Σ＊ → Σ＊ a következő tulajdonságokkal.
- w ∈ a ⇔ f (w) ∈ b minden W Σ Σ＊.
- az f függvényt egy Turing-gép kiszámíthatja minden w bemenetre egy polinom által határolt lépésekben |w / – ban.
ebben az esetben írunk egy ≤P B.
például, Legyen egy olyan nyelv, amely tartalmazza az összes grafikonok (kódolva adjacency mátrix), amelyek egy háromszög. (A háromszög egy ciklus hossza 3.) Legyen továbbá B az a nyelv, amely tartalmazza az összes mátrixok nem nulla nyoma. (A mátrix nyomai a fő átlós elemek összege.) Ezután a polinom-idő sok-egy redukálható B. ennek bizonyításához meg kell találnunk egy megfelelő transzformációs függvényt f. ebben az esetben beállíthatjuk f-et a szomszédsági mátrix 3.teljesítményének kiszámításához. Ehhez két mátrix-mátrix termékre van szükség, amelyek mindegyike polinom komplexitással rendelkezik.
triviálisan igaz, hogy L ≤P L. (be tudja bizonyítani hivatalosan?)
ezt most az NP-re alkalmazzuk.
a language L is NP-hard if and only if l’ ≤p L for every language L’ ∈ NP.
egy NP-kemény nyelv önmagában is lehet vagy nem.
a language L is NP-complete if and only if
- l ∈ NP and
- l is NP-hard.
a leghíresebb NP-teljes nyelv a SAT. Minden logikai képletet tartalmaz, amely elégedett lehet. Például (a ∨ b) ∧ (A ∨ b) SAT SAT . Egy érvényes tanú {a = 1, b = 0}. A képlet (a ∨ b) ∧ (A ∨ b) SAT B SAT SAT. (Hogyan bizonyítaná ezt?)
nem nehéz megmutatni, hogy a SAT ∈ NP. A SAT NP-keménységének bemutatása némi munka, de Stephen szakács 1971-ben készítette.
Miután az egyik NP-teljes Nyelv ismert volt, viszonylag egyszerű volt más nyelvek NP-teljességének csökkentése. Ha az a nyelv ismert, hogy NP-kemény, akkor azt mutatja, hogy a ≤P B azt mutatja, hogy a B NP-kemény is (a “≤p ” tranzitivitása révén). 1972-ben Richard Karp közzétett egy listát a 21 nyelven, hogy tudta mutatni voltak NP-teljes keresztül (tranzitív) csökkentése SAT. (Ez az egyetlen papír ebben a válaszban, amit valójában ajánlom, hogy olvassa el. A többiekkel ellentétben nem nehéz megérteni, és nagyon jó képet ad arról, hogyan működik az NP-teljesség bizonyítása a csökkentésen keresztül.)
végül egy rövid összefoglaló. Az NPH és NPC szimbólumokat használjuk az NP-hard és NP-complete nyelvek osztályainak jelölésére.
- p ⊆ NP
- NPC & subset; NP és NPC & részhalmaza; NPH, valójában NPC = NP ∩ NPH definíció szerint
- (a ∈ NP) ⇒ (B ∈ NPH) ⇒ a ≤P B
vegye figyelembe, hogy a felvétel NPC & részhészlet; NP akkor is megfelelő, ha P = NP. Ha látni szeretné ezt, tegye világossá, hogy egyetlen nem triviális nyelvet sem lehet triviálisra csökkenteni, és vannak triviális nyelvek A P-ben, valamint a nem triviális nyelvek az NP-ben. Ez egy (nem túl érdekes) sarok eset, bár.
a zavar elsődleges forrása úgy tűnik, hogy az “O(n ↦ f(n))” “n” – re gondolt, mint egy algoritmus bemenetének értelmezésére, amikor valójában a bemenet hosszára utal. Ez azért fontos különbség, mert azt jelenti, hogy egy algoritmus aszimptotikus komplexitása a bemenethez használt kódolástól függ.
Ezen a héten új rekordot ért el a legnagyobb ismert Mersenne prime. A legnagyobb jelenleg ismert prímszám 274 207 281 − 1. Ez a szám annyira hatalmas, hogy fejfájást okoz nekem, így a következő példában egy kisebbet fogok használni: 231 – 1 = 2 147 483 647. Különböző módon kódolható.
- a Mersenne kitevő, mint decimális szám:
31(2 byte) - mint decimális szám:
2147483647(10 bájt) - mint egyoperandusú száma:
11111…11, ahol a…helyébe 2 147 483 640 több1s (majdnem 2 GiB)
ezek a húrok kódolni ugyanazt a számot tekintve ezek közül bármelyik, akkor könnyen konstrukció más kódolási ugyanazt a számot. (A decimális kódolást bináris, oktális vagy hexadecimális kódolással helyettesítheti, ha szeretné. Csak állandó tényezővel változtatja meg a hosszúságot.)
a naiv algoritmus az elsődleges teszteléshez csak polinom az unary kódolásokhoz. Az AKS primality teszt polinom decimális (vagy bármely más B ≥ 2 bázis) esetén. A Lucas-Lehmer primality teszt a legismertebb algoritmus Mersenne prímek Mp p páratlan prím, de még mindig exponenciális a hossza a bináris kódolás a Mersenne exponens p (polinom p).
Ha egy algoritmus összetettségéről akarunk beszélni, nagyon fontos, hogy nagyon világos legyen, hogy milyen ábrázolást használunk. Általában feltételezhető, hogy a leghatékonyabb kódolást használják. Ez azt jelenti, hogy bináris egész számok. (Vegye figyelembe, hogy nem minden prímszám Mersenne prím, így a Mersenne exponens használata nem általános kódolási séma.)
az elméleti kriptográfiában számos algoritmust formálisan átadnak egy teljesen haszontalan k 1s karakterláncnak, mint az első paraméternek. Az algoritmus soha nem nézi ezt a paramétert, de lehetővé teszi, hogy formálisan polinom legyen k-ban, ami az eljárás biztonságának beállításához használt biztonsági paraméter.
Az egyes problémák, amelyek a határozat nyelv a bináris kódolás NP-teljes, a határozat nyelv már nem NP-teljes, ha a kódolás a beágyazott számok beállítása egyoperandusú. Az egyéb problémákra vonatkozó döntési nyelvek még akkor is NP-teljesek maradnak. Az utóbbiakat erősen NP-teljesnek nevezik. A legismertebb példa a bin csomagolás.
szintén (és talán még több) érdekes látni, hogyan változik egy algoritmus összetettsége, ha a bemenet tömörítve van. A Mersenne prímek példáján három kódolást láttunk, amelyek mindegyike logaritmikusan tömörebb, mint elődje.
1983-ban Hana Galperin és Avi Wigderson érdekes tanulmányt írtak a közös gráf algoritmusok összetettségéről, amikor a gráf bemeneti kódolása logaritmikusan tömörül. Ezekhez a bemenetekhez a felülről háromszöget tartalmazó grafikonok nyelve (ahol egyértelműen P-ben volt) hirtelen NP-teljessé válik.
és ez azért van, mert a nyelvosztályok, mint például a P és az NP, a nyelvekre vannak definiálva, nem pedig a problémákra.