Je “hebt eigenlijk gelijk over P en NP, maar niet over NP-hard en NP-compleet.

Om te beginnen, hier zijn de super beknopte definities van de vier complexiteitsklassen in kwestie:

• P is de klasse van beslissingsproblemen die in polynomiale tijd kunnen worden opgelost door een deterministische Turing-machine.

• NP is de klasse van beslissingsproblemen die in polynomiale tijd kunnen worden opgelost door een niet-deterministische Turing-machine. Evenzo is het de klasse van problemen die geverifieerd in polynomiale tijd door een deterministische Turing-machine.

• NP-hard is de klasse van beslissingsproblemen waartoe alle problemen in NP kunnen zijn teruggebracht tot in polynomiale tijd door een deterministische Turing-machine.

• NP-compleet is het snijpunt van NP-hard en NP. Op equivalente wijze is NP-compleet de klasse van beslissingsproblemen in NP waartoe alle andere problemen in NP in polynoomtijd kunnen worden teruggebracht door een deterministische Turingmachine.

En hier “sa Euler-diagram van Wikipedia met de relaties tussen deze vier klassen (aangenomen dat P niet gelijk is aan NP):

Het deel dat u naar ik aanneem het meest onbekend bent of waarmee u het meest verward bent is de notie van een “polynomiale tijdreductie” van probleem X naar probleem Y. Een reductie van X naar Y is simpelweg een algoritme A dat X oplost door gebruik te maken van een ander algoritme B dat probleem Y oplost. Deze reductie heet a ” polynoomtijdreductie “als alle delen van A anders dan B een polynoomtijdcomplexiteit hebben. Als een triviaal voorbeeld: het probleem van het vinden van het kleinste element in een array is constant in de tijd herleidbaar tot het sorteerprobleem, aangezien je de array kunt sorteren en vervolgens het eerste element van de gesorteerde array kunt retourneren.

Een wat gemakkelijk te missen is aan de NP-harde definitie, is dat de reductie gaat van NP-problemen naar het NP-harde probleem, maar niet noodzakelijkerwijs andersom . Dit betekent dat NP-harde problemen kunnen zijn in NP, of in een veel hogere complexiteitsklasse (zoals je kunt zien in het Euler-diagram), anders zijn het misschien niet eens beslisbare problemen.Daarom zeggen mensen vaak zoiets als “NP-hard betekent minstens zo hard als NP” wanneer ze dit informeel proberen uit te leggen.

Het stopprobleem is een goed voorbeeld van een NP-hard probleem dat “staat duidelijk niet in NP, zoals Wikipedia uitlegt :

Het is gemakkelijk om bewijzen dat het stopprobleem NP-hard is, maar niet NP-compleet. Het Booleaanse bevredigbaarheidsprobleem kan bijvoorbeeld worden gereduceerd tot het stopprobleem door het te transformeren naar de beschrijving van een Turing-machine die alle waarheidswaardetoekenningen uitprobeert en wanneer hij er een vindt die aan de formule voldoet, stopt hij en anders gaat hij in een oneindige lus. Het is ook gemakkelijk in te zien dat het stopprobleem niet in NP zit, aangezien alle problemen in NP beslissbaar zijn in een eindig aantal bewerkingen, terwijl het stopprobleem in het algemeen onbeslisbaar is.

Reacties

• @Nakano Intuïtief, het ‘ sa ” reductie ” in de zin dat van het ene probleem een subprobleem wordt gemaakt van een ander probleem. Het feit dat sommige van deze reducties de complexiteit vergroten in plaats van te verminderen door een slechte keuze van ” subprobleem “, betekent simpelweg dat u deze reducties nooit zou gebruiken in elke echte wereldcode. Al lijkt NP-hard me eerlijk gezegd wel een rare en niet erg interessante klas; het kan vruchtbaarder zijn om het te negeren en gewoon aan NP-complete te denken als de verzameling NP-problemen waartoe alle andere NP-problemen behoren.
• @Nakano stackoverflow.com/questions/12637582/… Ik denk dat het korte antwoord is dat wanneer mensen praten over integer-factorisatie als NP, ze ‘ hebben het normaal gesproken over hele grote gehele getallen, waarvoor je meestal je big-O-bewijzen begint met n als ” het aantal bits dat het gehele getal in beslag neemt in het geheugen ” in plaats van ” het aantal gehele getallen dat je hebt doorgegeven aan de functie “.
• @Nakano: in big-O-notatie is de n een maat voor de grootte van de invoer (aantal elementen, bytes, cijfers, enz.), Niet de waarde van de input.
• @Nakano Het korte antwoord is dat het ‘ goed gaat, en dit is waarom wanneer je tijd co mplexity analaysis je moet altijd specificeren wat n betekent . De bewering dat n ” de grootte van de invoer ” is, is slechts een beknopte samenvatting van hoe we normaal gesproken n definiëren. Het ‘ maakt geen deel uit van de rigoureuze definities van big-O-notatie of tijdcomplexiteit. Ik denk dat je gelijk hebt als je zegt dat factorisatie van gehele getallen O (sqrt (n)) is als n de waarde is van de invoer. Toevallig zijn de resultaten van complexiteit waarbij n betekent grootte in de praktijk meestal veel nuttiger dan die waarbij n waarde betekent.
• @Nakano It ‘ Het is ook de moeite waard om in gedachten te houden dat je technisch ook de tijdcomplexiteit van je primitieve bewerkingen moet definiëren (optellen, multitplicatie, uitlezen uit geheugen, schrijven naar geheugen, twee getallen vergelijken). Meestal gaan we ervan uit dat al deze primitieven constant zijn, of we tellen slechts één soort bewerking (bijv. Voor sorteeralgoritmen tellen we traditioneel de vergelijkingen). Ik vermoed dat de resultaten voor factorisatie van gehele getallen niet ‘ aannemen dat al deze bewerkingen een constante tijd zijn zoals we gewoonlijk doen, anders zou de grootte van het getal niet ‘ maakt niet veel uit.

Factorisatie van gehele getallen wordt aangehaald als een voorbeeld van NP, maar ik begrijp niet waarom het persoonlijk niet P is, aangezien factorisatie bij het testen O (sqrt (n)) tijd kost.

Voor de doeleinden van complexiteitsklassen is de n de lengte van de invoer. Dus als je integer k wilt ontbinden, is n niet k maar log k, het aantal bits (of wat dan ook) dat nodig is om het nummer op te schrijven. Factorisatie van gehele getallen is dus O(sqrt(k)) zoals u zegt, maar dit is O(sqrt(2n)) wat O(2(n/2)) is.

Ik neem aan dat NP-Hard vol met onbekenden zit. Moeilijk te verifiëren, moeilijk op te lossen.

Nee. NP-Hard gaat alleen over hoe moeilijk een probleem is om op te lossen.

NP-Hard problemen zijn op zijn minst het moeilijkste probleem in NP. We weten dat ze in ieder geval zo moeilijk zijn, want als we een polynoom-tijd algoritme hadden voor een NP-Hard probleem, zouden we dat algoritme aan elk probleem in NP kunnen aanpassen.

NP-Complete Ik begrijp het helemaal niet

NP- Volledig betekent dat een probleem zowel NP als NP-Hard is. Het betekent dat we snel een oplossing kunnen verifiëren (NP), maar het is minstens zo moeilijk als het moeilijkste probleem in NP (NP-Hard).

Ik weet niet echt wat het betekent dat het niet-deterministisch is.

Niet -determinisme is een alternatieve definitie van NP. Een niet-deterministische turingmachine is effectief in staat zichzelf op elk moment te dupliceren en elke duplicaat een ander uitvoeringspad te laten nemen. Onder deze definitie is NP de verzameling van problemen die in polynoomtijd kunnen worden opgelost door een computer die zichzelf vrijelijk kan dupliceren. Het blijkt dat dit precies dezelfde reeks problemen is die geverifieerd kunnen worden in polynomiale tijd.

Opmerkingen

• Het is dus mogelijk voor $ O ( n ^ k) $ tijdalgoritmen om NP-problemen te zijn?
• k is een constant reëel getal? Ja. Alle P-problemen zijn ook NP-problemen. Het is duidelijk dat alles wat je kunt oplossen in polynoomtijd ook geverifieerd kan worden in polynoomtijd.
• Hoe wordt lengte / grootte hier eigenlijk gedefinieerd? Ik zou bijvoorbeeld gewoon $ n $ in een grote basis kunnen schrijven en de lengte ervan kunnen verkleinen wanneer ik het schrijf. Hoe zit het met problemen die ‘ t niet expliciet omgaan met gehele getallen, maar bijvoorbeeld grafieken met $ V $ hoekpunten en $ E $ randen, enz.
• @Nakano, eigenlijk een grote basis zou het niet ‘ t veranderen, omdat het alleen een constant factorverschil zou zijn. Het zou dus geen ‘ polynoom versus niet-polynoom beïnvloeden. Als je het nummer echter unair zou schrijven, zou het het veranderen.
• @Nakano, hmm … ik zou ‘ t niet durven proberen de complexiteit uit te leggen lessen voor een vijfjarige. : P

Het eerste dat u moet begrijpen is dat P en NP classificeert talen , niet problemen . Om te begrijpen wat dit betekent, hebben we eerst enkele andere definities nodig.

Een alfabet is een niet-lege eindige set symbolen.

{0 , 1} 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.

Let Σ een alfabet zijn. Een geordende aaneenschakeling van een eindig aantal symbolen uit Σ wordt een woord over Σ .

De string 101 is een woord boven het alfabet {0, 1}. Het lege woord (vaak geschreven als ε ) is een woord boven elk alfabet. De tekenreeks penguin is een woord boven het alfabet dat de ASCII-tekens bevat. De decimale notatie van het getal π is geen woord boven het alfabet {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} omdat het niet eindig is.

Het 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 daarom eindig.

Laat Σ een alfabet zijn. De set Σ ^＊ bevat alle woorden van Σ , inclusief ε . De set Σ ⁺ bevat alle woorden van Σ , met uitzondering van ε . Voor n ∈ N , Σ ⁿ is de reeks woorden met een lengte n .

Voor elk alfabet Σ , Σ ^＊ en Σ ⁺ zijn oneindig telbare sets .Voor de ASCII-tekenset Σ _ASCII , de reguliere expressies .* en .+ duiden Σ _ASCII ^＊ en Σ _ASCII ⁺ respectievelijk.

{0, 1} ⁷ is de set van 7-bits ASCII-codes {0000000, 0000001,…, 1111111}. {0, 1} ³² is de set van 32 bits gehele getallen.

Laat Σ een alfabet zijn en L ⊆ Σ ^＊ . L wordt een taal genoemd via Σ .

Voor een alfabet Σ , de lege set en Σ ^＊ zijn triviale talen boven Σ . De eerste wordt vaak de lege taal genoemd. De lege taal {} en de taal die alleen het lege woord { ε } bevat, zijn verschillend.

De subset van {0, 1} ³² die overeenkomt met niet-NaN IEEE 754 drijvende-kommawaarden is een eindige taal.

Talen kunnen een oneindig aantal woorden bevatten, maar elke taal is telbaar. De reeks strings {1, 2,…} die de gehele getallen in decimale notatie aanduidt, is een oneindige taal boven het alfabet {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. De oneindige reeks strings {2, 3, 5, 7, 11, 13,…} die de priemgetallen in decimale notatie aanduidt, is een goede subset daarvan. De taal die alle woorden bevat die overeenkomen met de reguliere expressie [+-]?\d+\.\d*([eE][+-]?\d+)? is een taal boven de ASCII-tekenset (duidt een subset aan van de geldige drijvende-komma-expressies zoals gedefinieerd door de programmeertaal C).

Er is geen taal die alle reële getallen bevat (in welke notatie dan ook) omdat de reeks reële getallen niet kan worden geteld.

Let Σ is een alfabet en L ⊆ Σ ^＊ . Een machine D beslist L als voor elke invoer w ∈ Σ ^＊ het berekent de karakteristieke functie χ _L ( w ) in eindige tijd. De karakteristieke functie is gedefinieerd als

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

Zon machine wordt een beslisser voor L . We schrijven “ D ( w ) = x ” voor “gegeven w , D geeft x ”.

Er zijn veel machinemodellen. De meest algemene die tegenwoordig praktisch wordt gebruikt, is het model van een Turing-machine . Een Turing-machine heeft onbeperkte lineaire opslag, geclusterd in cellen. Elke cel kan op elk moment precies één symbool van een alfabet bevatten. De Turing-machine voert zijn berekening uit als een reeks berekeningsstappen. Bij elke stap kan het één cel lezen, eventueel de waarde ervan overschrijven en de lees- / schrijfkop één positie naar de linker- of rechtercel verplaatsen. Welke actie de machine zal uitvoeren, wordt bestuurd door een eindige-toestandsautomaat.

Een willekeurige-toegangsmachine met een eindige set instructies en onbeperkte opslag is een ander machinemodel dat net zo krachtig is als het Turing-machinemodel.

Omwille van deze discussie zullen we ons niet lastig vallen met het precieze machinemodel dat we gebruiken, maar eerder voldoende te zeggen dat de machine een eindige deterministische besturingseenheid heeft, onbeperkte opslagruimte en een berekening uitvoert als een reeks stappen dat kan worden geteld.

Aangezien u “het in uw vraag hebt gebruikt, neem ik aan dat u” al bekend bent met “big-O” -notatie dus hier is slechts een korte opfriscursus.

Let f : N → een functie zijn.De set O ( f ) bevat alle functies g : N → N waarvoor constanten bestaan n ₀ ∈ N en c ∈ N zodanig dat voor elke n ∈ N met n > n ₀ het is waar 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 beslist L en een constante k ∈ N zodat voor elke invoer w , D stopt na maximaal T (| w |) stappen voor een functie T ∈ O ( n ↦ n ^k ).

Sinds O ( n ↦ n ^k ), hoewel het wiskundig correct is, is het lastig om te schrijven en te lezen, maar de meeste mensen – om eerlijk te zijn, iedereen behalve ikzelf – schrijven meestal gewoon O(n^k ).

Merk op dat de binding afhangt van de lengte van w . Daarom is het argument dat je maakt voor de taal van de priemgetallen alleen correct voor getallen in unaray-coderingen , waarbij voor de codering w van een getal n , de lengte van de codering | w | is evenredig met n . Niemand zou in de praktijk ooit zon codering gebruiken. Door een geavanceerder algoritme te gebruiken dan simpelweg alle mogelijke factoren uit te proberen, kan echter worden aangetoond dat de taal van priemgetallen in P blijft als de invoer in binair (of naar een andere basis) is gecodeerd. (Ondanks enorme belangstelling kon dit alleen worden bewezen door Manindra Agrawal, Neeraj Kayal en Nitin Saxena in een bekroonde paper in 2004, dus u kunt raden dat de algoritme is niet erg eenvoudig.)

De triviale talen {} en Σ ^＊ en de niet-triviale taal { ε } staan uiteraard in P (voor elk alfabet Σ ). Kun je functies in je favoriete programmeertaal schrijven die een string als invoer nemen en een booleaanse waarde retourneren die aangeeft of de string een woord is uit de taal voor elk van deze en bewijzen dat je functie een polynoom run-time complexiteit heeft?

Elke gewone taal (een taal die wordt beschreven door een reguliere expressie) is in P .

Laat Σ een alfabet zijn en L ⊆ Σ ^＊ . Een machine V die een gecodeerde tupel van twee woorden w , c ∈ Σ ^＊ en geeft 0 of 1 weer nadat een eindig aantal stappen een verifier voor L als het de volgende eigenschappen heeft.

• Gegeven ( w , c ), V geeft alleen 1 weer als w ∈ L .
• Voor elke w ∈ L is er bestaat een c ∈ Σ ^＊ zodanig dat V ( w , c ) = 1.

De c in de bovenstaande definitie wordt een getuige (of certificaat ) genoemd .

Een verificateur mag fout-negatieven geven voor de verkeerde getuige, zelfs als w daadwerkelijk in L staat. Het is echter niet toegestaan om false positives te geven. Het is ook vereist dat er voor elk woord in de taal ten minste één getuige is.

Voor de taal COMPOSITE, die de decimale coderingen bevat van alle gehele getallen die niet primair zijn kan een getuige een factorisatie zijn. (659, 709) is bijvoorbeeld een getuige voor 467231 ∈ SAMENSTELLING. U kunt gemakkelijk verifiëren dat op een vel papier zonder dat de getuige wordt gegeven, het bewijzen dat 467231 niet primair is moeilijk zou zijn zonder een computer te gebruiken.

We hebben niets gezegd over hoe een geschikte getuige kan zijn gevonden Dit is het niet-deterministische deel.

De klasse NP bevat alle talen L waarvoor er een Turing-machine bestaat V die L en een constante k ∈ N verifieert zodat voor elke input ( w , c ), V stopt na maximaal T (| w |) stappen voor een functie T ∈ O ( n ↦ n^k ).

Merk op dat de bovenstaande definitie impliceert dat voor elke w ∈ L er een getuige c bestaat met | c | ≤ T (| w |). (De Turing-machine kan onmogelijk naar meer symbolen van de getuige kijken.)

NP is een superset van P (waarom?). Het is niet bekend of er talen bestaan die in NP maar niet in P staan.

Factorisatie van gehele getallen is geen taal per se. We kunnen echter een taal construeren die het beslissingsprobleem vertegenwoordigt dat ermee verbonden is. Dat wil zeggen, een taal die alle tupels ( n , m ) bevat zodanig dat n een factor d heeft met d ≤ m . Laten we deze taal FACTOR noemen. Als je een algoritme hebt om FACTOR te bepalen, kan het worden gebruikt om een volledige factorisatie te berekenen met alleen polynoomoverhead door een recursieve binaire zoekopdracht uit te voeren voor elke priemfactor.

Het is gemakkelijk aan te tonen dat FACTOR zich in NP . Een geschikte getuige is simpelweg de factor d zelf en het enige dat de verificateur hoeft te doen, is verifiëren dat d ≤ m en n mod d = 0. Dit alles kan gedaan worden in polynomiale tijd. (Onthoud nogmaals dat het de lengte van de codering is die telt en dat is logaritmisch in n .)

Als je kunt aantonen dat FACTOR ook in P staat, kun je er zeker van zijn dat je veel coole onderscheidingen krijgt. (En je hebt een aanzienlijk deel van de huidige cryptografie verbroken.)

Voor elke taal in NP is er een brute-force-algoritme dat beslist het deterministisch. Het voert eenvoudig een uitputtende zoekopdracht uit over alle getuigen. (Merk op dat de maximale lengte van een getuige wordt begrensd door een polynoom.) Dus uw algoritme om te beslissen dat PRIMES eigenlijk een brute-force algoritme was om COMPOSITE te beslissen.

Om uw laatste vraag te beantwoorden, moeten we reductie introduceren. Reducties zijn een zeer krachtig concept van theoretische informatica. Het ene probleem reduceren tot het andere betekent in feite het ene probleem oplossen door een ander op te lossen probleem.

Laat Σ een alfabet zijn en A en B zijn talen boven Σ . A is polynoom-tijd veel-een reduceerbaar tot B als er een functie f bestaat: Σ ^＊ → Σ ^＊ met de volgende eigenschappen.

• w ∈ A   ⇔   f ( w ) ∈ B   voor iedereen w ∈ Σ ^＊ .
• De functie f kan worden berekend door een Turing-machine voor elke invoer w in een aantal stappen begrensd door een polynoom in | w |.

In dit geval schrijven we A ≤ _p B .

Voor Laat bijvoorbeeld A de taal zijn die alle grafieken bevat (gecodeerd als aangrenzende matrix) die een driehoek bevatten. (Een driehoek is een cyclus van lengte 3.) Laat verder B de taal zijn die alle matrices bevat met een spoor anders dan nul. (Het spoor van een matrix is de som van de belangrijkste diagonale elementen.) Dan is A polynoom-tijd veel-een reduceerbaar tot B . Om dit te bewijzen, moeten we een geschikte transformatiefunctie f vinden. In dit geval kunnen we f instellen om de 3 ^e macht van de aangrenzende matrix te berekenen. Hiervoor zijn twee matrix-matrixproducten nodig, die elk een polynoomcomplexiteit hebben.

Het is triviaal waar dat L ≤ _p L . (Kunt u het formeel bewijzen?)

We “passen dit nu toe op NP .

Een taal L is NP -hard als en slechts als L “≤ _p L voor elke taal L ” ∈ NP .

Een NP -hard taal kan al dan niet in NP zelf zijn.

Een taal L is NP -complete als en slechts als

• L ∈ NP en
• L is NP -hard.

De meest bekende NP -complete taal is SAT. Het bevat alle booleaanse formules waaraan kan worden voldaan. Bijvoorbeeld: ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Een geldige getuige is { a = 1, b = 0}. De formule ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Hoe zou je dat bewijzen?)

Het is niet moeilijk om aan te tonen dat SAT ∈ NP . Het is wat werk om de NP -hardheid van SAT te laten zien, maar het werd in 1971 gedaan door Stephen Cook .

Zodra die ene NP -complete taal bekend was, was het relatief eenvoudig om de NP -compleetheid van andere talen via reductie te laten zien. Als bekend is dat taal A NP -hard is, laat dan zien dat A ≤ _p B laat zien 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 -volledig waren via (transitieve) reductie van SAT. (Dit is het enige artikel in dit antwoord dat ik je eigenlijk aanraad om te lezen. In tegenstelling tot de andere, is het niet moeilijk te begrijpen en geeft het een heel goed idee van hoe het bewijzen van NP -volledigheid via reductie werkt. )

Tot slot een korte samenvatting. We gebruiken de symbolen NPH en NPC om de klassen van NP -hard en NP -complete talen aan te duiden respectievelijk.

• P ⊆ NP
• NPC ⊂ NP en NPC ⊂ NPH , eigenlijk NPC = NP ∩ NPH per definitie
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Merk op dat de opname NPC ⊂ NP juist is, zelfs in het geval dat P = NP . Om dit te zien, moet u duidelijk maken dat geen niet-triviale taal kan worden teruggebracht tot een triviale en dat er ook triviale talen zijn in P als niet-triviale talen in NP . Thi s is echter een (niet erg interessante) zaak.

Addendum

Je primaire bron van verwarring lijkt te zijn dat je dacht aan de “ n ”in“ O ( n ↦ f ( n )) ”Als de interpretatie van de invoer van een algoritme, terwijl het in feite verwijst naar de lengte van de invoer. Dit is een belangrijk onderscheid omdat het betekent dat de asymptotische complexiteit van een algoritme afhangt van de codering die voor de invoer wordt gebruikt.

Deze week is er een nieuw record voor de grootste bekende Mersenne prime is bereikt. Het grootste momenteel bekende priemgetal is 2 ^{74   207   281} – 1. Dit aantal is zo enorm dat ik er hoofdpijn van krijg, dus gebruik ik een kleinere in het volgende voorbeeld: 2 ³¹ – 1 = 2   147   483   647. Het kan op verschillende manieren worden gecodeerd.

• door zijn Mersenne-exponent als decimaal getal: 31 (2 bytes)
• als decimaal getal: 2147483647 (10 bytes)
• als unair nummer: 11111…11 waarbij de … moet worden vervangen door 2   147   483   640 meer 1 s (bijna 2 GiB)

Al deze strings coderen voor hetzelfde nummer en gegeven een van deze, kunnen we gemakkelijk elke andere codering van hetzelfde nummer construeren. (u kunt decimale codering vervangen door binaire, octale of hexadecimetalen). mal als je 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 een polynoom voor decimaal (of een andere grondtal b ≥ 2 ).De Lucas-Lehmer primaliteitstest is het bekendste algoritme voor Mersenne priemgetallen M _p 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 het willen hebben over de complexiteit van een algoritme, is het erg belangrijk dat we heel duidelijk zijn welke representatie we gebruiken. Over het algemeen kan worden aangenomen 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 krijgen veel algoritmen formeel een volledig nutteloze reeks van k 1 s als de eerste parameter. Het algoritme kijkt nooit naar deze parameter, maar staat het formeel toe om een polynoom te zijn in k , wat de beveiligingsparameter gebruikt om de beveiliging van de procedure af te stemmen.

Voor sommige problemen waarvoor de beslissingstaal bij binaire codering NP -volledig is, is de beslissingstaal niet langer NP -volledig als de codering van ingebedde nummers is omgeschakeld naar unair. De beslissingstalen voor andere problemen blijven zelfs dan NP -volledig. Deze laatste worden sterk NP -complete genoemd. Het bekendste voorbeeld is bin packing .

Het is ook (en misschien wel meer) interessant om te zien hoe de complexiteit van een algoritme verandert als de invoer gecomprimeerd is. Voor het voorbeeld van Mersenne-priemgetallen hebben we drie coderingen gezien, die elk logaritmisch meer gecomprimeerd zijn dan hun voorganger.

In 1983 Hana Galperin en Avi Wigderson heeft een interessant artikel geschreven over de complexiteit van veelgebruikte grafiekalgoritmen wanneer de invoercodering van de grafiek logaritmisch wordt gecomprimeerd. Voor deze invoer wordt de taal van grafieken die een driehoek van bovenaf bevatten (waar het duidelijk in P stond) plotseling NP -volledig.

En dat “s omdat taallessen zoals P en NP zijn gedefinieerd voor talen , niet voor problemen .

Opmerkingen

• Dit antwoord is waarschijnlijk niet nuttig voor het begripsniveau van de vragensteller. Lees de andere antwoorden en kijk waar Nanako mee worstelt. Denk je dat dit antwoord zal hem / haar helpen?
• Dit antwoord helpt OP misschien niet, maar helpt zeker andere lezers (inclusief ikzelf).
• zeer nuttig antwoord! zou moeten overwegen om de wiskundige symbolen niet goed te corrigeren weergegeven.

Ik zal proberen je een minder informele definitie voor hetzelfde te geven.

P-problemen: problemen die kunnen worden opgelost in polynoomtijd. Bevat problemen die efficiënt kunnen worden opgelost.

NP-probleem: problemen die kunnen worden geverifieerd in polynoom mial tijd. Bijvoorbeeld: handelsreiziger, circuitontwerp. NP-problemen zijn een soort puzzels (zoals sudoku). Als we een juiste oplossing voor het probleem hebben, kunnen we onze oplossing heel snel controleren, maar als we het echt proberen op te lossen, kan het een eeuwigheid duren.

Nu vraagt P vs NP eigenlijk of een probleem dat snel kan worden opgelost gecontroleerd om correct te zijn, dan is er altijd een snelle manier om het op te lossen. Dus in wiskundig termen schrijven: is NP een subset van P of niet?

Nu komend terug naar NP compleet: dit zijn de echt moeilijke problemen van de NP-problemen. Daarom, als er een snellere manier is om NP complete op te lossen, wordt NP compleet P en vallen NP-problemen samen in P.

NP hard: problemen die zelfs niet in de polynoomtijd kunnen worden gecontroleerd, zijn np moeilijk. Het kiezen van de beste zet bij het schaken is er bijvoorbeeld één van.

Als iets onduidelijk blijft, probeer dan deze video te bekijken: https://www.youtube.com/watch?v=YX40hbAHx3s

Ik hoop dat dit een wazige contour zal opleveren.