het eerste ding om te begrijpen is dat P en NP classificeren talen, niet problemen. Om te begrijpen wat dit betekent, hebben we eerst een aantal andere definities nodig.
Een alfabet is een niet-lege eindige verzameling symbolen.
{01} is een alfabet, net als de ASCII-tekenset. {} is geen alfabet omdat het leeg is. N (de gehele getallen) is geen alfabet omdat het niet eindig is.
zij Σ Een alfabet. Een geordende aaneenschakeling van een eindig aantal symbolen uit Σ wordt een woord over Σ genoemd.
de tekenreeks 101 is een woord over het alfabet {01}. Het lege woord (vaak geschreven als ε) is een woord over elk alfabet. De tekenreeks penguin is een woord over het alfabet dat de ASCII-tekens bevat. De decimale notatie van het getal π is niet een woord over het alfabet {.0123456789} want het is niet eindig.
De lengte van een woord w, geschreven als |w|, is het aantal symbolen erin.
bijvoorbeeld, |hello| = 5 en |ε| = 0. Voor elk woord w,| w / ∈ N en dus eindig.
zij Σ Een alfabet. De verzameling Σ＊ bevat alle woorden over Σ, inclusief ε. De verzameling Σ + bevat alle woorden boven Σ, met uitzondering van ε. Voor n ∈ N is Σn de verzameling woorden met lengte n.
voor elk alfabet Zijn Σ, Σ＊ En Σ+ oneindige aftelbare verzamelingen. Voor de ASCII-tekenset ΣASCII geven de reguliere expressies .* en .+ respectievelijk ΣASCII＊ en ΣASCII+ aan.
{01}7 is de set van 7-bit ASCII-codes {00000000000001111111101}32 is de verzameling van 32 bit integer waarden.
zij Σ Een alfabet en L ⊆ Σ＊. L wordt een taal over Σ genoemd.
voor een alfabet Σ zijn de lege verzameling en Σ＊ triviale talen over Σ. De eerste taal wordt vaak de lege taal genoemd. De lege taal {} en de taal die alleen het lege woord {ε} bevat zijn verschillend.
de deelverzameling van {01}32 die overeenkomt met niet-NaN IEEE 754 drijvende-kommawaarden is een eindige taal.
talen kunnen een oneindig aantal woorden hebben, maar elke taal is aftelbaar. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. De oneindige reeks strings {23571113, …} het aangeven van de priemgetallen in decimale notatie is een juiste subset daarvan. De taal die alle woorden bevat die overeenkomen met de reguliere expressie ?\d+\.\d*(?\d+)? is een taal over de ASCII-tekenset (een subset van de geldige floating-point-expressies zoals gedefinieerd door de programmeertaal C).
Er is geen taal die alle reële getallen bevat (in een notatie) omdat de verzameling van reële getallen niet aftelbaar is.
zij Σ Een alfabet en L ⊆ Σ＊. Een machine D bepaalt L of voor elke input w ∈ Σ＊ de karakteristieke functie xL(w) in eindige tijd wordt berekend. De karakteristieke functie wordt gedefinieerd als
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.zo ’n machine wordt een decider voor L. We schrijven” D(w) = x “voor”gegeven w, D uitgangen x”.
Er zijn veel machinemodellen. De meest algemene die tegenwoordig in de praktijk wordt gebruikt is het model van een Turing machine. Een Turing machine heeft onbeperkte lineaire opslag geclusterd in cellen. Elke cel kan precies één symbool van een alfabet bevatten op elk moment in de tijd. De Turing machine voert zijn berekening uit als een opeenvolging van berekeningsstappen. In elke stap kan het één cel lezen, mogelijk de waarde overschrijven en de lees – /schrijfkop met één positie naar de linker-of rechtercel verplaatsen. Welke actie de machine zal uitvoeren wordt gecontroleerd door een eindige toestand automaat.
een random access machine met een eindige set instructies en onbeperkte opslag is een ander machinemodel dat even krachtig is als het Turing machinemodel.
in het belang van deze discussie zullen we ons niet bezighouden met het precieze machinemodel dat we gebruiken, maar volstaan om te zeggen dat de machine een eindige deterministische regeleenheid heeft, onbeperkte opslagruimte en een berekening uitvoert als een opeenvolging van stappen die kunnen worden geteld.
omdat je het in je vraag hebt gebruikt, neem ik aan dat je al bekend bent met “big-O” notatie, dus hier is slechts een snelle opfriscursus.
Laat f: N → een functie zijn. De verzameling O(f) bevat alle functies g: N → N waarvoor constanten n0 N n en c ∈ n bestaan, zodat voor elke N N N met n > n0 het waar is dat g(n) ≤ c f (n).
nu zijn we bereid om de echte vraag te benaderen.
De klasse P bevat alle talen L waarvoor er een Turing machine D bestaat die bepaalt L en een constante k N N zodanig dat Voor elke input w, d stopt na ten hoogste t(|w|) stappen voor een functie T ∈ O(n ↦ nk).
aangezien o(n ↦ NK), hoewel wiskundig correct is, lastig is om te schrijven en te lezen, schrijven de meeste mensen – om eerlijk te zijn, iedereen behalve ikzelf – meestal gewoon O(nk).
merk op dat de binding afhangt van de lengte van w. daarom is het argument dat u maakt voor de taal van de priemgetallen alleen correct voor getallen in unaray-coderingen, waar voor de codering w van een getal n de lengte van de codering |w| evenredig is met n. niemand zou ooit een dergelijke codering in de praktijk gebruiken. Met behulp van een geavanceerder algoritme dan gewoon proberen alle mogelijke factoren, kan echter worden aangetoond dat de taal van priemgetallen blijft in P als de ingangen zijn gecodeerd in binair (of naar een andere basis). (Ondanks de enorme belangstelling, kon dit alleen worden bewezen door Manindra Agrawal, Neeraj Kayal, en Nitin Saxena in een bekroonde paper in 2004, dus je kunt raden dat het algoritme is niet erg eenvoudig.)
de triviale talen {} en Σ＊ en de niet-triviale taal {ε} zijn duidelijk in P (voor elk alfabet Σ). Kun je functies in je favoriete programmeertaal schrijven die een string als input nemen en een Booleaanse teruggeven die vertelt of de string een woord is uit de taal voor elk van deze en bewijzen dat je functie veelterm run-time complexiteit heeft?
elke reguliere taal (een taal die wordt beschreven door een reguliere expressie) is in P.
zij Σ Een alfabet en L ⊆ Σ＊. Een machine V die een gecodeerde tupel van twee woorden w, c Σ Σ＊ neemt en 0 of 1 uitgangen na een eindig aantal stappen is een verificateur voor L als het de volgende eigenschappen heeft.
- gegeven (w, c), geeft V 1 alleen uit als w L. L.
- voor elke w L L bestaat er een c Σ Σ＊ zodanig dat V(w, c) = 1.
De c in de bovenstaande definitie wordt een getuige (of certificaat) genoemd.
een verificateur mag valse negatieven geven voor de verkeerde getuige, zelfs als w daadwerkelijk in L. staat, maar het is niet toegestaan valse positieven te geven. Het is ook vereist dat Voor elk woord in de taal, er ten minste één getuige bestaat.
voor het taalcomposiet, dat de decimale coderingen bevat van alle gehele getallen die geen priemgetal zijn, kan een getuige een factorisatie zijn. Bijvoorbeeld, (659, 709) is een getuige voor 467231 COMPOSITE COMPOSITE. U kunt gemakkelijk controleren dat op een vel papier, terwijl zonder de getuige gegeven, bewijzen dat 467231 is niet priemgetal zou moeilijk zijn zonder het gebruik van een computer.
we hebben niets gezegd over hoe een geschikte getuige gevonden kan worden. Dit is het niet-deterministische deel.
De klasse NP bevat alle talen L waarvoor er een Turing machine V bestaat die L en een constante k ∈ N zodanig verifieert dat Voor elke invoer (w, c), V stopt na maximaal t(|w|) stappen voor een functie T ∈ O(n ↦ nk).
merk op dat de bovenstaande definitie impliceert dat er voor elke w L L een getuige c met |C| ≤ T(|w|) bestaat. (De Turing machine kan onmogelijk meer symbolen van de getuige bekijken.)
NP is een superset van P (waarom?). Het is niet bekend of er talen bestaan die in NP staan, maar niet in P.
Integer factorisatie is geen taal op zich. We kunnen echter een taal construeren die het beslissingsprobleem vertegenwoordigt dat ermee samenhangt. Dat wil zeggen, een taal die alle tupels (n, m) bevat, zodat n een factor d heeft met d ≤ m. Laten we deze taalfactor noemen. Als u een algoritme hebt om FACTOR te bepalen, kan het worden gebruikt om een volledige factorisatie te berekenen met alleen polynomiale overhead door een recursieve binaire zoekopdracht uit te voeren voor elke priemfactor.
Het is gemakkelijk om aan te tonen dat de FACTOR in NP zit. Een geschikte getuige zou eenvoudigweg de factor d zelf zijn en de verificateur zou alleen moeten controleren of d ≤ m en n mod d = 0. Dit alles kan worden gedaan in polynomiale tijd. (Onthoud nogmaals dat het de lengte van de codering is die telt en dat logaritmisch is in n.)
Als u kunt laten zien dat de FACTOR ook in P staat, kunt u er zeker van zijn dat u veel coole awards krijgt. (En je hebt een aanzienlijk deel van de cryptografie van vandaag gebroken.)
voor elke taal in NP is er een brute-force algoritme dat het deterministisch bepaalt. Het voert gewoon een uitputtende zoektocht uit over alle getuigen. (Merk op dat de maximale lengte van een getuige wordt begrensd door een veelterm. Dus, uw algoritme om priemgetallen te beslissen was eigenlijk een brute-force algoritme om composiet te beslissen.
om uw laatste vraag te beantwoorden, moeten we reductie invoeren. Reducties zijn een zeer krachtig concept van theoretische informatica. Het ene probleem tot het andere reduceren betekent in feite het oplossen van een probleem door het oplossen van een ander probleem.
zij Σ Een alfabet en A en B talen over Σ. A is polynoom-tijd veel-één reduceerbaar tot B als er een functie f bestaat: Σ＊ → Σ＊ met de volgende eigenschappen.
- w ∈ A f f (w) B B voor alle w Σ Σ＊.
- de functie f kan door een Turingmachine worden berekend voor elke input w in een aantal stappen begrensd door een polynoom in |w|.
in dit geval schrijven we A ≤p B.
bijvoorbeeld, laat a de taal zijn die alle grafieken bevat (gecodeerd als adjacency matrix) die een driehoek bevatten. (Een driehoek is een cyclus van lengte 3.) Zij verder B de taal die alle matrices met niet-nul spoor bevat. (Het spoor van een matrix is de som van de belangrijkste diagonale elementen.) Dan is a polynoom – tijd veel-één reduceerbaar tot B. Om dit te bewijzen, moeten we een geschikte transformatiefunctie vinden f. In dit geval kunnen we f Instellen om de 3e macht van de adjacency matrix te berekenen. Dit vereist twee matrixmatrixproducten, die elk veeltermcomplexiteit hebben.
Het is triviaal waar dat L ≤p L. (kunt u het formeel bewijzen?)
We zullen dit nu toepassen op NP.
een taal L is dan en alleen dan NP-hard als L’ ≤p L voor elke taal L’ ∈ NP.
een NP-harde taal kan al dan niet in NP zelf staan.
een taal L is NP-compleet als en alleen als
- L ∈ NP en
- L is NP-hard.
de beroemdste NP-complete taal is SAT. Het bevat alle Booleaanse formules waaraan kan worden voldaan. Bijvoorbeeld, (A b b) ∧ (A ∨ b) SAT SAT. Een geldige getuige is {a = 1, b = 0}. De formule (A b b) ∧ (a ∨ b) ∧ B SAT zat. (Hoe zou je dat bewijzen?)
Het is niet moeilijk om aan te tonen dat SAT ∈ NP. Om de NP-hardheid van SAT aan te tonen is wat werk maar het werd gedaan in 1971 door Stephen Cook.
zodra die ene NP-volledige taal bekend was, was het relatief eenvoudig om de NP-volledigheid van andere talen aan te tonen via reductie. Als taal A bekend is als NP-hard, dan toont aan dat A ≤p B dat B ook NP-hard is (via de transitiviteit van “≤p”). In 1972 publiceerde Richard Karp een lijst van 21 talen waarvan hij kon aantonen dat ze NP-compleet waren via (transitieve) reductie van SAT. (Dit is het enige papier in dit antwoord dat ik eigenlijk raad je moet lezen. In tegenstelling tot de andere, is het niet moeilijk te begrijpen en geeft het een zeer goed idee van hoe het bewijzen van NP-volledigheid via reductie werkt.)
tenslotte een korte samenvatting. We zullen de symbolen NPH en NPC gebruiken om de klassen NP-hard en NP-complete talen aan te duiden.
- P ⊆ NP
- NPC & subset; NP en NPC ⊂ NPH, eigenlijk NPC = NP ∩ NPH per definitie
- (A ∈ NP) ∧ (B ∈ NPH) ⇒ a ≤p B
merk op dat de inclusie NPC ⊂ NP is juist, zelfs in het geval dat P = NP. Om dit te zien, maak jezelf duidelijk dat geen enkele niet-triviale taal kan worden gereduceerd tot een triviale taal en er zijn triviale talen in P evenals niet-triviale talen in NP. Dit is echter een (niet erg interessant) hoekje.
uw primaire bron van verwarring lijkt te zijn dat u dacht aan de “n” in “O(n ↦ f(n))” als de interpretatie van de invoer van een algoritme wanneer het eigenlijk verwijst naar de lengte van de invoer. Dit is een belangrijk onderscheid omdat het betekent dat de asymptotische complexiteit van een algoritme afhankelijk is van de codering die voor de invoer wordt gebruikt.
Deze week werd een nieuw record voor het grootste bekende mersennepriem bereikt. Het grootste momenteel bekende priemgetal is 274 207 281 − 1. Dit nummer is zo groot dat het me hoofdpijn geeft, dus Ik zal een kleinere gebruiken in het volgende voorbeeld: 231 – 1 = 2 147 483 647. Het kan op verschillende manieren worden gecodeerd.
- door de Mersenne exponent als decimaal getal:
31(2 bytes) - als decimaal getal:
2147483647(10 bytes) - als unaire aantal:
11111…11waarbij de…vervangen moet worden door 2 147 483 640 meer1s (bijna 2 GiB)
Al deze snaren coderen hetzelfde nummer en krijgt een van deze, kunnen we gemakkelijk construct een andere codering van hetzelfde nummer. (U kunt decimale codering vervangen door binair, octaal of hexadecimaal als u wilt. Het verandert alleen de lengte met een constante factor.)
het naïeve algoritme voor het testen van primaliteit is alleen polynoom voor unaire coderingen. De AKS-primaliteitstest is polynoom voor decimaal (of een andere base b ≥ 2). De Lucas-Lehmer-primaliteitstest is het bekendste algoritme voor Mersenne-priemgetallen Mp met p een oneven priemgetal, maar het is nog steeds exponentieel in de lengte van de binaire codering van de Mersenne-exponent p (polynoom in p).
als we willen praten over de complexiteit van een algoritme, is het erg belangrijk dat we heel duidelijk zijn welke representatie we gebruiken. In het algemeen kan men aannemen dat de meest efficiënte codering wordt gebruikt. Dat wil zeggen, binair voor gehele getallen. (Merk op dat niet elk priemgetal een Mersenne-priemgetal is, dus het gebruik van de Mersenne-exponent is geen algemeen coderingsschema.)
in theoretische cryptografie worden veel algoritmen formeel doorgegeven aan een volledig nutteloze string van k 1s als de eerste parameter. Het algoritme kijkt nooit naar deze parameter, maar het staat het toe om formeel polynoom te zijn in k, wat de veiligheidsparameter is die wordt gebruikt om de veiligheid van de procedure af te stemmen.
voor sommige problemen waarvoor de decisietaal in binaire codering NP-compleet is, is de decisietaal niet langer NP-compleet als de codering van ingesloten getallen wordt overgeschakeld naar unary. De beslissingstalen voor andere problemen blijven zelfs dan NP-compleet. Deze laatste worden sterk NP-compleet genoemd. Het bekendste voorbeeld is bin packaging.
Het is ook (en misschien meer) interessant om te zien hoe de complexiteit van een algoritme verandert als de invoer wordt gecomprimeerd. Voor het voorbeeld van Mersenne priemgetallen hebben we drie coderingen gezien, die logaritmisch meer gecomprimeerd zijn dan zijn voorganger.
in 1983 hebben Hana Galperin en Avi Wigderson een interessant artikel geschreven over de complexiteit van gemeenschappelijke grafiekalgoritmen wanneer de invoercodering van de grafiek logaritmisch wordt gecomprimeerd. Voor deze ingangen wordt de taal van grafieken met een driehoek van boven (waar het duidelijk in P was) plotseling NP-compleet.
en dat komt omdat taalklassen zoals P en NP zijn gedefinieerd voor talen, niet voor problemen.