Alapvetően igazad van a P-vel és az NP-vel kapcsolatban, de az NP-hard és NP-teljesekkel kapcsolatban nem.

A kezdőknek itt a szóban forgó négy komplexitási osztály szuper tömör meghatározása:

• P a döntési problémák osztálya, amelyet polinomiális időben megoldhat egy determinisztikus Turing-gép.

• Az NP a döntési problémák osztálya, amelyet polinom időben megoldhat egy nem determinisztikus Turing-gép. Ezzel egyenértékűen a problémák osztálya ellenőrizhető polinom időben, egy determinisztikus Turing-gép segítségével.

• Az NP-hard az a döntési probléma osztály, amelyre az NP összes problémája felosztható. egy determinisztikus Turing-gép által polinomiális időre redukálva.

• Az NP-teljes az NP-hard és az NP metszéspontja. Hasonlóképpen, az NP-complete az NP azon döntési problémáinak osztálya, amelyre az NP összes többi problémája polinomiális időben redukálható egy determinisztikus Turing-gép segítségével.

És itt “sa Euler-diagram a Wikipédiából , amely bemutatja a kapcsolatokat e négy osztály között (feltételezve, hogy P nem egyenlő az NP-vel):

Az a rész, amelyet feltételezem, hogy Ön nem ismer jobban vagy zavaros a “polinomiális időcsökkentés” fogalma az X problémától az Y problémáig. Az X-ről Y-re történő redukció egyszerűen egy A algoritmus, amely X megoldja valamilyen más B algoritmus felhasználásával, amely megoldja az Y problémát. Ezt a redukciót ” polinomiális időcsökkentés “, ha az A nem B összes részének polinomiális időbonyolultsága van. Triviális példaként a tömb legkisebb elemének megtalálásának problémája állandó időben csökkenthető a rendezési problémára, mivel rendezheti a tömböt, majd visszaadhatja a rendezett tömb első elemét.

Egy az a nehéz, hogy az NP-hard definícióból hiányzik az, hogy a csökkentés az NP-problémákról az NP-nehéz problémákra megy át, de nem feltétlenül fordítva . Ez azt jelenti, hogy az NP-nehéz problémák lehetnek NP-ben, vagy egy sokkal magasabb komplexitási osztályban (amint az az Euler-diagramból is látszik), vagy lehet, hogy nem is eldönthető problémák.Ezért az emberek gyakran olyasmit mondanak, hogy “NP-hard azt jelenti, hogy legalább olyan kemény, mint az NP”, amikor informálisan próbálják megmagyarázni ezeket a dolgokat.

A leállási probléma jó példa egy NP-nehéz problémára, amely “nyilvánvalóan nem NP-ben vannak, amint a a Wikipédia megmagyarázza :

Könnyű bizonyítani, hogy a leállási probléma NP-nehéz, de nem NP-teljes. Például a Boole-féle elégedettségi probléma redukálható a leállítási problémára azáltal, hogy átalakítja azt egy Turing-gép leírásává, amely minden igazságérték-hozzárendelést kipróbál, és amikor talál olyat, amely kielégíti a leállított képletet, és egyébként végtelen ciklusba kerül. Az is könnyen belátható, hogy a leállítási probléma nem az NP-ben van, mivel az NP-ben minden probléma véges számú műveletnél eldönthető, míg a leállítási probléma általában nem eldönthetetlen.

Megjegyzések

• @Nakano Intuitív módon ‘ sa ” csökkentés ” abban az értelemben, hogy az egyik probléma valamilyen más probléma részproblémájává válik. Az a tény, hogy ezek a csökkentések némelyike növeli a bonyolultságot ahelyett, hogy csökkentené a ” alprobléma ” rossz megválasztása révén, egyszerűen azt jelenti, hogy soha nem használná ezeket a csökkentéseket bármilyen valós kódban. Bár őszinte legyek, az NP-hard furcsa és nem is túl érdekes osztálynak tűnik; gyümölcsözőbb lehet figyelmen kívül hagyni, és csak az NP-complete-ra gondolni, mivel az NP-problémák halmaza, amelyre az összes többi NP-probléma csökkent.
• @Nakano stackoverflow.com/questions/12637582/… Úgy gondolom, hogy a rövid válasz az, hogy amikor az emberek arról beszélnek, hogy az egész számozás NP, akkor ‘ általában valóban hatalmas egész számokról beszélnek, amelyekhez általában elkezdi elvégezni a nagy-O bizonyításokat n-vel, mint ” az egész szám által a memóriában elfoglalt bitek száma ” a ” helyett a ” függvénybe átadott egész számok száma.
• @Nakano: Nagy-O jelölésben a n a bemenet méretének (elemek, bájtok, számjegyek stb.) Mértéke, nem pedig a bemenet.
• @Nakano A rövid válasz az, hogy ‘ minden rendben van, és ezért, amikor az időt mplexity analaysis mindig meg kell adni, hogy mit jelent az n . Az állítás, miszerint n ” a bemenet mérete “, csak egy tömör összefoglaló arról, hogy mi szokott úgy dönteni, hogy meghatározzuk az n-t. ‘ nem része a big-O jelölés vagy az idő bonyolultságának szigorú meghatározásának. Úgy gondolom, hogy helyesen mondja azt, hogy az egész faktorizáció O (sqrt (n)), amikor n az input értéke . Csak úgy történik, hogy a bonyolultsági eredmények, ahol n azt jelenti, hogy a méret általában sokkal hasznosabb a gyakorlatban, mint azok, amelyekben az n értéke.
• @Nakano It ‘ s azt is érdemes szem előtt tartani, hogy technikailag meg kell határoznia primitív műveleteinek időbeli összetettségét is (összeadás, multiplikáció, olvasás memóriából, írás memóriába, két szám összehasonlítása). Legtöbbször vagy feltételezzük, hogy ezek a primitívek állandóak, vagy csak egyfajta műveletet számolunk (például algoritmusok rendezéséhez hagyományosan számoljuk az összehasonlításokat). Gyanítom, hogy az egész számolás eredményei nem feltételezik, hogy ezek a műveletek állandó időtartamúak, mint általában, egyébként a szám mérete nem lenne ‘ t nagyon fontos.

Az integer faktorosítást az NP példaként említjük, de nem értem, hogy miért nem személyesen P, mivel a próba faktorizálása O (sqrt (n)) időt vesz igénybe.

A bonyolultsági osztályok szempontjából a n a bemenet hossza. Tehát, ha a k egész számot szeretné figyelembe venni, akkor a n nem k, hanem log k, a bitek száma (vagy bármi más), ami a szám felírásához szükséges. Tehát az egész számozás O(sqrt(k)), ahogy mondod, de ez O(sqrt(2n)), amely O(2(n/2)).

Feltételezem, hogy az NP-Hard csak tele van ismeretlenekkel. Nehéz ellenőrizni, nehéz megoldani.

Nem. Az NP-Hard pusztán arról szól, hogy egy problémát milyen nehéz megoldani.

Az NP-Hard problémák legalább nehézek, mint a legnehezebbek az NP-ben. Tudjuk, hogy legalább ilyen kemények, mert ha polinomidõs algoritmusunk lenne egy NP-Hard problémára, akkor ezt az algoritmust az NP bármely problémájához igazíthatnánk.

NP-Complete Egyáltalán nem értem

NP- A komplett azt jelenti, hogy a probléma mind az NP, mind az NP-Hard. Ez azt jelenti, hogy a megoldást gyorsan ellenőrizhetjük (NP), de legalább olyan nehéz, mint a legnehezebb probléma az NP-ben (NP-Hard).

Nem igazán tudom, mit jelent, ha nem determinisztikus.

Nem -determinizmus az NP alternatív meghatározása. A nem-determinisztikus turinggép hatékonyan képes bármikor lemásolni önmagát, és mindegyik más-más végrehajtási utat választ. Ezen meghatározás szerint az NP azon problémák összessége, amelyeket polinom időben megoldhat egy számítógép, mint amennyit szabadon lemásolhat. Kiderült, hogy ez pontosan ugyanaz a problémakészlet, amelyet polinomiális időben ellenőrizhetünk.

Megjegyzések

• Tehát lehetséges $ O ( n ^ k) $ time algoritmusok NP-problémák?
• k állandó valós szám? Igen. Az összes P probléma egyben NP probléma is. Nyilvánvaló, hogy bármi, amit megoldhat a polinom időben, a polinom időben is ellenőrizhető.
• Hogyan határozható meg itt valójában a hossz / méret? Például egyszerűen írhatnék $ n $ -ot egy nagy alapba, és csökkenthetném a hosszát, amikor írok. Mi a helyzet azokkal a problémákkal, amelyek nem ‘ nem foglalkoznak kifejezetten egész számokkal, de mondanak grafikonokat $ V $ csúcsokkal és $ E $ élekkel stb.
• @Nakano, valójában egy nagy alap nem változtatná meg, ‘ mivel ez csak állandó tényező-különbség lenne. Tehát nem lenne ‘ t hatással polinom vs nem polinom. Ha azonban a számot unáriában írta, akkor az megváltoztatná.
• @Nakano, hmm … Nem merném ‘ meg merem próbálni magyarázni a bonyolultságot osztályok ötéves korig. : P

Először meg kell érteni, hogy P és NP osztályozza a nyelveket , nem pedig a problémákat . Ahhoz, hogy megértsük, mit jelent ez, először néhány más definícióra van szükségünk.

Egy ábécé egy nem üres véges szimbólumkészlet.

{0 , 1} egy ábécé, csakúgy, mint az ASCII karakterkészlet. A (z) {} nem ábécé, mert üres. A N (az egész szám) nem ábécé, mert nem véges.

Legyen Σ legyen ábécé. A Σ véges számú szimbólumának rendezett összefűzését szónak nevezzük át Σ .

A karakterlánc 101 egy szó az {0, 1} ábécé fölött. Az üres szó (gyakran ε néven írva) minden ábécé fölötti szó. A penguin karakterlánc az ASCII karaktereket tartalmazó ábécé fölötti szó. A π szám tizedesjegye nem egy szó az {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, mert ez nem véges.

A | w | néven írt w szó hossza a szimbólumok száma benne.

Például | hello | = 5 és | ε | = 0. Bármely szóra w , | w | ∈ N és ezért véges.

Legyen Σ legyen ábécé. A (z) Σ ^＊ halmaz az összes szót tartalmazza: Σ , beleértve a ε t is. A Σ ⁺ halmaz tartalmazza az összes szót, amely feletti Σ , kivéve a ε t. A következőhöz: n ∈ N , Σ n a n hosszúságú szavak halmaza.

minden ábécé Σ , Σ ^＊ és Σ ⁺ végtelen megszámlálható halmazok .Az ASCII karakterkészlet Σ _ASCII esetében a .* és .+ jelöli Σ _ASCII ^＊ és Σ _ASCII ⁺ .

{0, 1} ⁷ a 7 bites ASCII-kódok halmaza {0000000, 0000001,…, 1111111}. {0, 1} ³² a 32 bites egész értékek halmaza.

Legyen Σ ábécé, és L ⊆ Σ ^＊ . Az L -t nyelvnek hívják Σ .

Ábécé Σ esetén a az üres halmaz és a Σ ^＊ triviális nyelvek Σ . Az előbbit gyakran üres nyelv nek nevezik. Az üres nyelv {} és az a nyelv, amely csak az { ε } szót tartalmazza, különböznek egymástól.

A {0, 1} ³² amely nem NaN IEEE 754 lebegőpontos értékeknek felel meg, véges nyelv.

A nyelveknek végtelen számú szavuk lehet, de minden nyelv megszámlálható. Az egész számokat tizedesjelben jelölő {1, 2,…} karakterláncok végtelen nyelvek az {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. A végtelen húrkészlet: {2, 3, 5, 7, 11, 13,…}, amelyek decimális jelöléssel jelzik a prímszámokat, ennek megfelelő részhalmaza. A [+-]?\d+\.\d*([eE][+-]?\d+)? reguláris kifejezésnek megfelelő összes szót tartalmazó nyelv az ASCII karakterkészlet fölötti nyelv (amely az érvényes lebegőpontos kifejezések részhalmazát jelöli a C programozási nyelv által definiált módon). / p>

Nincs olyan nyelv, amely minden valós számot tartalmazna (bármilyen jelölésben), mert a valós számok halmaza nem számlálható.

Legyen Σ legyen ábécé és L ⊆ Σ ^＊ . Egy gép D úgy dönt, hogy L ha minden bemenetre w ∈ Σ ^＊ kiszámítja a jellemző függvényt χ _L ( w ) véges idő alatt. A karakterisztikus függvény a következő:

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Egy ilyen gépet decidernek neveznek a L számára. Azt írjuk, hogy „ D ( w ) = x ” a „megadott w , D outputok x ”.

Sok gépi modell létezik. A legáltalánosabb, amely manapság gyakorlati használatban van, egy Turing gép modellje. Egy Turing-gép korlátlan lineáris tárolást tartalmaz cellákba tömörítve. Minden cellában pontosan egy ábécé szimbóluma lehet az idő bármely pontján. A Turing-gép a számítást a számítási lépések sorozataként hajtja végre. Minden lépésben képes elolvasni egy cellát, esetleg felülírni az értékét, és az olvasási / írási fejet egy pozícióval elmozdítani a bal vagy a jobb cellába. A gép által végrehajtott műveletet egy véges állapotú automata vezérli.

A véges utasításkészlettel és korlátlan tárhelyű véletlen hozzáférésű gép egy másik gépi modell, amely ugyanolyan nagy teljesítményű, mint a Turing-gép modellje.

Ennek a megbeszélésnek a kedvéért nem fog minket zavarni az általunk használt pontos gépmodell, hanem elégséges azt mondani, hogy a gépnek véges determinisztikus vezérlőegysége van, korlátlan tárhelye van, és a lépések sorozataként végez számítást ez megszámolható.

Mivel már felhasználta a kérdésében, feltételezem, hogy Ön már ismeri a „big-O” jelölést , tehát itt csak egy gyors frissítés található.

Legyen f : N → legyen függvény.A O ( f ) halmaz tartalmazza az összes függvényt g : N → N amelyeknél léteznek konstansok n ₀ ∈ N és c ∈ N oly módon, hogy minden n ∈ N a n > n ₀ it igaz, hogy g ( n ) ≤ c f ( n ).

Most felkészültünk a valós kérdés megközelítésére.

A P osztály minden olyan nyelvet tartalmaz, L amelyhez létezik egy Turing-gép D , amely eldönti L és egy állandó k ∈ N olyan, hogy minden bemenetre w , D leáll legfeljebb T (| w |) lépések után egy T O ( n ↦ n ^k ).

Mivel O ( n ↦ n ^k ), bár matematikailag helytálló, de írni és olvasni kényelmetlen, az emberek többsége – hogy őszinte legyek, mindenki, kivéve én magam – általában egyszerűen ír O>(n^k ).

Ne feledje, hogy a megkötés a w . Ezért a prímek nyelvére vonatkozó argumentum csak a unaray kódolásokban található számok esetében helyes, ahol a w kódolásához egy szám n , a kódolás hossza | w | arányos a n vel. Ilyen kódolást a gyakorlatban soha senki nem használna. Fejlettebb algoritmus alkalmazásával, mint az összes lehetséges tényező kipróbálása, megmutatható azonban, hogy a prímszámok nyelve P ben marad, ha a bemenetek binárisan vannak kódolva (vagy bármely más alapra). (A hatalmas érdeklődés ellenére ezt csak Manindra Agrawal, Neeraj Kayal és Nitin Saxena bizonyíthatta egy 2004-ben egy díjnyertes lapban, így sejtheti, hogy a az algoritmus nem túl egyszerű.)

A triviális nyelvek {} és Σ ^＊ és a nem triviális nyelv { ε } nyilvánvalóan P -ban szerepel (bármilyen ábécé esetében) Σ ). Írhat-e olyan függvényeket a kedvenc programozási nyelvén, amelyek bevesznek egy karakterláncot, és logikai értéket adnak vissza, amely megmondja, hogy a karakterlánc szó-e az egyes nyelvek nyelvéből, és be tudja bizonyítani, hogy a függvénye polinom futásidejű bonyolult?

Minden normál nyelv (egy reguláris kifejezés által leírt nyelv) a P nyelven található.

Legyen Σ ábécé, és L ⊆ Σ ^＊ . V gép, amely két szó kódolt dupláját veszi: w , c ∈ Σ ^＊ és véges számú lépés után 0 vagy 1 értéket ad ki ellenőrző L esetén, ha a következő tulajdonságokkal rendelkezik.

• Adva ( w , c ), V csak akkor adja ki az 1-et, ha w ∈ L .
• Minden w ∈ L létezik egy c ∈ Σ ^＊ oly módon, hogy V ( w , c ) = 1.

A fenti meghatározásban szereplő c t tanú nak (vagy tanúsítvány nak) nevezzük .

A hitelesítő hamis negatívumokat adhat meg a rossz tanúk esetében, még akkor is, ha w valójában L -ben van. Nem szabad azonban hamis pozitív eredményt adni. Szükség van arra is, hogy a nyelv minden egyes szavához legyen legalább egy tanú.

A COMPOSITE nyelv esetében, amely tartalmazza az összes nem prím egész szám tizedes kódolását , a tanú tényező lehet. Például a (659, 709) a 467231 ∈ COMPOSITE tanúja. Könnyedén ellenőrizheti, hogy egy papírlapon, anélkül, hogy tanú lenne, bebizonyí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 a megfelelő tanút hogyan lehet Ez a nem determinisztikus rész.

A NP osztály tartalmazza az összes olyan nyelvet L , amelyhez létezik Turing-gép V amely ellenőrzi az L és egy állandó k ∈ N értéket, amely minden bemenet ( w , c ), V legfeljebb T után áll le (| | w |) lépései egy T ∈ O ( n n^k ).

Ne feledje, hogy a fenti definíció azt jelenti, hogy minden w ∈ L esetében létezik tanú c | c | ≤ T (| w |). (A Turing-gép nem tudja megnézni a tanú további szimbólumait.)

NP a P szuperhalmaza (miért?). Nem ismert, hogy léteznek-e olyan nyelvek, amelyek NP nyelven vannak, de nem P nyelven vannak.

Az egész faktorizálás önmagában nem nyelv. Készíthetünk azonban egy nyelvet, amely a hozzá kapcsolódó döntési problémát képviseli. Vagyis egy nyelv, amely tartalmazza az összes sorrendet ( n , m ) oly módon, hogy a n tényezője d d ≤ m . Nevezzük ezt a nyelvet FACTOR-nak. Ha van algoritmusa a FACTOR eldöntésére, akkor az felhasználható a teljes faktorizáció kiszámításához, csak polinom rezsivel, rekurzív bináris kereséssel az egyes prímtényezőkre.

Könnyű kimutatni, hogy a FACTOR NP . A megfelelő tanú egyszerűen maga a d tényező lenne, és az ellenőrnek csak annyit kellene tennie, hogy ellenőrizze, hogy d ≤ m és n mod d = 0. Mindez polinomiális időben elvégezhető. (Emlékezzünk ismét arra, hogy a kódolás hossza számít, és ez logaritmikus a n -ben.]

Ha be tudja mutatni, hogy a FACTOR is szerepel a P ben, akkor biztosan sok jó díjat kap. (És megtörted a mai kriptográfia jelentős részét.)

A NP nyelv minden nyelvéhez létezik egy nyers erővel rendelkező algoritmus, amely dönt ez determinisztikusan. Egyszerűen kimerítő keresést végez minden tanú felett. (Vegye figyelembe, hogy a tanú maximális hosszát polinom határolja.) Tehát, a PRIMES eldöntésére szolgáló algoritmusod egy durva erő algoritmusa volt a COMPOSITE eldöntésére. p>

Az utolsó kérdés megválaszolásához be kell vezetnünk a redukció t. A redukciók az elméleti számítástechnika nagyon erős fogalma. Az egyik probléma csökkentése a másikra alapvetően azt jelenti, hogy az egyik problémát egy másik megoldásával oldják meg. probléma.

Legyen Σ ábécé, és A és a B nyelv Σ feletti nyelv. A polinom-idő sok-egy redukálható B re, ha létezik 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 bemenetre w polinommal határolt számos lépésben | w |.

Ebben az esetben A ≤ _p B .

Például legyen A az a nyelv, amely tartalmazza az összes grafikont (szomszédsági mátrixként kódolva), amely háromszöget tartalmaz. (A háromszög egy 3 hosszúságú ciklus.) Legyen további B az a nyelv, amely az összes nulla nélküli nyomot tartalmazó mátrixot tartalmazza. (A mátrix nyoma a fő átlós elemeinek összege.) Ekkor A polinomi-idő sok-egy redukálható B re. Ennek bizonyításához meg kell találnunk egy megfelelő transzformációs függvényt f . Ebben az esetben beállíthatjuk az f et a szomszédsági mátrix 3 ^rd teljesítményének kiszámításához. Ehhez két mátrix-mátrix termékre van szükség, amelyek mindegyike polinomi komplexitású.

Triviálisan igaz, hogy L ≤ _p L . (Formálisan be tudja bizonyítani?)

Ezt most a NP -re alkalmazzuk.

Egy L nyelv NP -kemény és csak akkor, ha L “≤ _p L minden nyelvre L ” ∈ NP .

Egy NP -kemény nyelv lehet, hogy nem benne van a NP -ben.

Egy L nyelv NP -complete csak akkor, ha

• L ∈ NP és
• L NP -kemény.

A leghíresebb NP -teljes nyelv a SAT. Minden boolean képletet tartalmaz, amely kielégíthető. Például: ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Érvényes tanú: { a = 1, b = 0}. Képlet ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Ezt hogyan bizonyítanád?)

Nem nehéz megmutatni, hogy a SAT ∈ NP . A SAT NP -keménységének bemutatása némi munka, de ezt 1971-ben Stephen Cook végezte el.

Miután ismerte ezt az egy NP -teljes nyelvet, viszonylag egyszerű volt más nyelvek NP -teljességét csökkentéssel bemutatni. Ha az A nyelvről ismert, hogy NP -kemény, akkor megmutatja, hogy A ≤ _p B azt mutatja, hogy a B is NP -kemény (a „ _p ”). 1972-ben Richard Karp közzétette a 21 nyelvet tartalmazó listát, amely NP -teljesnek bizonyult a SAT (transzitív) redukcióján keresztül. (Ez az egyetlen cikk ebben a válaszban, amelyet valójában ajánlom, olvassa el. A többiekkel ellentétben nem nehéz megérteni, és nagyon jó képet ad arról, hogyan működik a NP teljességének bizonyítása redukcióval. )

Végül egy rövid összefoglaló. Az NPH és az NPC szimbólumokkal jelöljük a NP -kemény és NP -teljes nyelv osztályait rendre.

• P ⊆ NP>
• NPC ⊂ NP és NPC ⊂ NPH , valójában NPC = NP ∩ NPH definíció szerint
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Ne feledje, hogy az NPC ⊂ NP felvétele még abban az esetben is megfelelő, ha P = NP . Ennek megtekintéséhez tisztázza magát, hogy egyetlen nem triviális nyelv sem redukálható triviálissá, és vannak triviális nyelvek a P ben is mint nem triviális nyelvek a NP ben. Thi s egy (nem túl érdekes) sarokeset.

Kiegészítés

Úgy tűnik, hogy az elsődleges zavarodottságod az, hogy a „ n ”itt:„ O ( n ↦ f ( n )) ”, Mint egy algoritmus bemenetének értelmezése , amikor valójában a bemenet hosszára utal. Ez azért fontos megkülönböztetés, mert ez azt jelenti, hogy egy algoritmus aszimptotikus bonyolultsága függ a bemenethez használt kódolástól.

Ezen a héten új rekord a legnagyobb ismert Mersenne prime teljesítésre került. A jelenleg ismert legnagyobb prímszám 2 ^{74   207   281} – 1. Ez a szám olyan hatalmas hogy fejfájást okoz nekem, ezért a következő példában kisebbet fogok használni: 2 ³¹ – 1 = 2   147   483   647. Különböző módon kódolható.

• Mersenne-kitevője decimális számként: 31 (2 byte)
• decimális számként: 2147483647 (10 byte)
• unary szám: 11111…11 ahol a … szöveget 2   147   483   640 további 1 s (majdnem 2 GiB)

Mindezek a karakterláncok ugyanazt a számot kódolják, és ezek bármelyikével könnyen megkonstruálhatjuk ugyanannak a számnak bármely más kódolását. mal, ha akarod. Csak állandó tényezővel változtatja meg a hosszúságot.)

A primitás tesztelésére szolgáló naiv algoritmus csak uniar kódolások esetén polinom. Az AKS elsődleges teszt polinom decimális (vagy bármely más alap b ≥ 2 ).A Lucas-Lehmer primalitás teszt a legismertebb algoritmus a Mersenne-prímekhez M _p p nélkül páratlan prím, de még mindig exponenciális a Mersenne-kitevő p bináris kódolásának hosszában (polinom a p ).

Ha egy algoritmus bonyolultságáról akarunk beszélni, nagyon fontos, hogy világosan tisztázzuk, milyen ábrázolást használunk. Általában feltételezhető, hogy a leghatékonyabb kódolást használják. Vagyis bináris egész számokra. (Ne feledje, hogy nem minden prímszám Mersenne-prím, ezért a Mersenne-kitevő használata nem általános kódolási séma.)

Az elméleti kriptográfiában sok algoritmus formálisan átmegy egy teljesen haszontalan k 1 s mint első paraméter. Az algoritmus soha nem nézi ezt a paramétert, de lehetővé teszi, hogy formailag polinom legyen a k ban, amely a biztonsági paraméter az eljárás biztonságának hangolására szolgál.

Néhány olyan probléma esetén, amelynél a bináris kódolás döntési nyelve NP -teljes, a döntési nyelv már nem NP -teljes, ha a beágyazott számok kódolása unárissá vált. A többi probléma döntési nyelve akkor is NP -teljes marad. Ez utóbbiakat erősen NP -teljes nek hívják. A legismertebb példa a bin packing .

Az is érdekes (és talán még érdekesebb), hogy hogyan az algoritmus bonyolultsága megváltozik, ha a bemenetet tömörítik . A Mersenne-prímek példájára három kódolást láthattunk, amelyek mindegyike logaritmikusan tömörített, mint elődje.

1983-ban Hana Galperin és Avi Wigderson érdekes cikket írt a közös gráfalgoritmusok bonyolultságáról, amikor a gráf bemeneti kódolását logaritmikusan tömörítik. Ezeknél a bemeneteknél a felülről háromszöget tartalmazó grafikonok nyelve (ahol egyértelműen a P -ban volt) hirtelen NP -telenné válik.

És ez “, mert a nyelvi osztályok, például a P és a NP a nyelvek re vannak meghatározva, nem a problémák ra.

Megjegyzések

• Ez a válasz valószínűleg nem hasznos a kérdező megértése szempontjából. Olvassa el a többi választ, és nézze meg, mivel küzd Nanako. A válasz segít neki / neki?
• Ez a válasz nem biztos, hogy segíti az OP-t, de természetesen segít más olvasóknak (beleértve magam is).
• nagyon hasznos válasz! fontolja meg a matematikai szimbólumok nem megfelelő javítását megjelenik.

Igyekszem kevésbé informális meghatározást adni ugyanarra.

P problémák: olyan problémák, amelyek polinomiális időben megoldhatók. Olyan problémákat tartalmaz, amelyek hatékonyan megoldhatók.

NP probléma: a polyno területén ellenőrizhető problémák fiola ideje. Például: utazó eladó, áramköri tervezés. Az NP problémák olyanok, mint a rejtvények (például a sudoku). Megfelelő megoldást adva a problémára, nagyon gyorsan ellenőrizhetjük a megoldást, de ha valóban megpróbáljuk megoldani, akkor ez örökké tarthat.

Most a P vs NP valóban megkérdezi, hogy van-e olyan probléma, amelynek megoldása gyorsan megoldható ellenőrizni, hogy helyes-e, akkor mindig van-e gyors módja annak megoldására. Így matematikailag írva: az NP a P részhalmaza vagy sem?

Most visszatérve az NP-re teljes: ezek az NP-problémák nagyon nehéz problémái. Ezért ha az NP complete megoldásának van egy gyorsabb módja, akkor az NP complete P-vé válik, és az NP-problémák P-be esnek.

NP hard: azok a problémák, amelyek még polinomiális időben sem ellenőrizhetők, np nehézek. Például a sakk legjobb mozdulatának kiválasztása az egyik.

Ha valami továbbra sem világos, próbáld meg megnézni ezt a videót: https://www.youtube.com/watch?v=YX40hbAHx3s

Remélem, hogy ez elmosódott kontúrt eredményez.