den første ting at forstå er, at P og NP klassificerer sprog, ikke problemer. For at forstå, hvad det betyder, har vi brug for nogle andre definitioner først.
et alfabet er et ikke-tomt endeligt sæt symboler.
{01} er et alfabet, ligesom ASCII-tegnsættet. {} er ikke et alfabet, fordi det er tomt. N (heltalene) er ikke et alfabet, fordi det ikke er endeligt.
lad Lira være et alfabet. En ordnet sammenkædning af et endeligt antal symboler fra Karrus kaldes et ord over karrus.
strengen101er et ord over alfabetet {01}. Det tomme ord (ofte skrevet som Kurt) er et ord over ethvert alfabet. Strengen penguin er et ord over alfabetet, der indeholder ASCII-tegnene. Decimalnotationen af tallet prisT er ikke et ord over alfabetet {.01234567889} fordi det ikke er endeligt.
længden af et ord m, skrevet som |M|, er antallet af symboler i det.
f.eks. |hello | = 5 og |ret| = 0. For ethvert ord b, |b| l og derfor endeligt.
lad Lira være et alfabet. Sættet indeholder alle ord over karrus, inklusive karrus. Den indstillede kursist + indeholder alle ord over kursisten, undtagen kursisten. For n-kursen N er kursen sæt af ord med længde n.
for hvert alfabet er Kurren, kurren og kurren+ uendelige tællelige sæt. For ASCII-tegnsættet, er de regulære udtryk .*og .+ betegner hhv.
{01}7 er sættet med 7-bit ASCII-koder {00000000000001111111101} 32 er sættet med 32 bit heltalværdier.
lad Lira være et alfabet og L& undergruppe; Lira. L kaldes et sprog over Kurt.
for et alfabetkrus er det tomme sæt og krysantemum trivielle sprog over krysantemum. Førstnævnte kaldes ofte det tomme sprog. Det tomme sprog {} og det sprog, der kun indeholder det tomme ord {List}, er forskellige.
delmængden af {01}32, der svarer til ikke-Nan IEEE 754 flydende punktværdier, er et endeligt sprog.
sprog kan have et uendeligt antal ord, men hvert sprog kan tælles. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Det uendelige sæt strenge {23571113, …} betegner primtalene i decimalnotation er en ordentlig delmængde deraf. Sproget, der indeholder alle ord, der matcher det regulære udtryk ?\d+\.\d*(?\d+)? er et sprog over ASCII-tegnsættet (betegner en delmængde af de gyldige flydende udtryk som defineret af C programmeringssprog).
der er ikke noget sprog, der indeholder alle reelle tal (i nogen notation), fordi sættet med reelle tal ikke kan tælles.
lad Lira være et alfabet og L& undergruppe; Lira. En maskine D bestemmer L, hvis for hver indgang B &i; Den beregner den karakteristiske funktion i endelig tid. Den karakteristiske funktion er defineret som
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.en sådan maskine kaldes en decider for L. Vi skriver” D(H) = H “for”givet h, d udgange h”.
Der er mange maskinmodeller. Den mest generelle, der er i praktisk brug i dag, er modellen af en Turing-maskine. En Turing-maskine har ubegrænset lineær opbevaring grupperet i celler. Hver celle kan indeholde nøjagtigt et symbol på et alfabet på ethvert tidspunkt. Turing-maskinen udfører sin beregning som en sekvens af beregningstrin. I hvert trin kan den læse en celle, muligvis overskrive dens værdi og flytte læse/skrivehovedet med en position til venstre eller højre celle. Hvilken handling maskinen vil udføre styres af en endelig tilstandsautomat.
en tilfældig adgangsmaskine med et begrænset sæt instruktioner og ubegrænset opbevaring er en anden maskinmodel, der er lige så kraftig som Turing-maskinmodellen.
af hensyn til denne diskussion skal vi ikke genere os med den præcise maskinmodel, vi bruger, men snarere tilstrækkeligt til at sige, at maskinen har en endelig deterministisk kontrolenhed, ubegrænset opbevaring og udfører en beregning som en sekvens af trin, der kan tælles.
da du har brugt det i dit spørgsmål, antager jeg, at du allerede er bekendt med “big-O” notation, så her er kun en hurtig genopfriskning.
lad f: n ret være en funktion. Sættet O(f) indeholder alle funktioner g: n-kur N, for hvilke der findes konstanter n0-kur n og c-kur n sådan, at for hver n-kur n med n > n0 er det sandt, at g(n) – kur c f (n).
nu er vi parat til at nærme os det virkelige spørgsmål.
klassen p indeholder alle sprog L, for hvilke der findes en Turing-maskine D, der bestemmer L og en konstant k-værdi N sådan, at D for hver indgang B stopper efter højst T (|vægt/) trin for en funktion T-værdi O(n-værdi nk).
da O(n p > er matematisk korrekt, er det ubelejligt at skrive og læse, de fleste mennesker – for at være ærlige, alle undtagen mig selv – skriver normalt simpelthen O(nk).
Bemærk, at bundet afhænger af længden af V. derfor er argumentet, du fremsætter for primernes sprog, kun korrekt for tal i unaray-kodninger, hvor for kodningen v af et tal n, længden af kodningen| m / er proportional med n. ingen ville nogensinde bruge en sådan kodning i praksis. Ved hjælp af en mere avanceret algoritme end blot at prøve alle mulige faktorer, kan det dog vises, at sproget for primtal forbliver i P, hvis inputene er kodet i binær (eller til en hvilken som helst anden base). (På trods af massiv interesse kunne dette kun bevises af Manindra Agraval, Neeraj Kayal og Nitin Sachsena i et prisvindende papir i 2004, så du kan gætte, at algoritmen ikke er meget enkel.)
de trivielle sprog {} og Krar og det ikke-trivielle sprog {Krar} er naturligvis i P (for ethvert alfabet Krar). Kan du skrive funktioner på dit foretrukne programmeringssprog, der tager en streng som input og returnerer en boolsk, der fortæller, om strengen er et ord fra sproget for hver af disse og bevise, at din funktion har polynomisk køretidskompleksitet?
hvert regulært sprog (et sprog beskrevet af et regulært udtryk) er i P.
lad Lira være et alfabet og L &delmængde; Lira. En maskine V, der tager en kodet tupel med to ord v, c-kur og udgange 0 eller 1 Efter et endeligt antal trin, er en verifikator for L, Hvis den har følgende egenskaber.
- givet (B, c), V udgange 1 kun hvis B-L.
- for hver b-l findes der en c-l, således at v(b, c) = 1.
c i ovenstående definition kaldes et vidne (eller certifikat).
en verifikator har lov til at give falske negativer for det forkerte vidne, selvom vi faktisk er i L. Det er dog ikke tilladt at give falske positive. Det kræves også, at der for hvert ord på sproget findes mindst et vidne.
for sprogkompositten, der indeholder decimalkodninger af alle heltal, der ikke er primære, kan et vidne være en faktorisering. For eksempel (659, 709)er et vidne til 467231 Lira COMPOSITE. Du kan nemt kontrollere, at på et ark papir, mens uden vidnet givet, at bevise, at 467231 er ikke prime ville være vanskeligt uden at bruge en computer.
vi sagde ikke noget om, hvordan et passende vidne kan findes. Dette er den ikke-deterministiske del.
klassen NP indeholder alle sprog L, for hvilke der findes en Turing-maskine V, der verificerer L og en konstant k-ret N sådan, at V for hver indgang (H, c) stopper efter højst T (|h/) Trin for en funktion T-Ret O(n-ret nk).
Bemærk, at ovenstående definition indebærer, at der for hver v-l findes et vidne c med| c| – L (|B/). (Turing-maskinen kan umuligt se på flere symboler på vidnet.)
NP er et supersæt af P (hvorfor ?). Det vides ikke, om der findes sprog, der er i NP, men ikke i P.
Heltalsfaktorisering er ikke et sprog i sig selv. Vi kan dog konstruere et sprog, der repræsenterer det beslutningsproblem, der er forbundet med det. Det vil sige et sprog, der indeholder alle tupler (n, m), således at n har en faktor d med d &lekv; m. lad os kalde denne sprogfaktor. Hvis du har en algoritme til at bestemme faktor, kan den bruges til at beregne en fuld faktorisering med kun polynomisk overhead ved at udføre en rekursiv binær søgning efter hver primfaktor.
det er let at vise, at faktoren er i NP. Et passende vidne ville simpelthen være selve faktoren d, og alt, hvad verifikatoren skulle gøre, er at kontrollere, at d &lekv; m og n mod d = 0. Alt dette kan gøres i polynomisk tid. (Husk igen, at det er længden af kodningen, der tæller, og det er logaritmisk i n.)
Hvis du kan vise, at faktoren også er i P, kan du være sikker på at få mange seje priser. (Og du har brudt en betydelig del af dagens kryptografi.)
for hvert sprog i NP er der en brute-force algoritme, der bestemmer det deterministisk. Det udfører simpelthen en udtømmende søgning over alle vidner. (Bemærk, at den maksimale længde af et vidne er afgrænset af et polynom.) Så din algoritme til at bestemme primtal var faktisk en brute-force algoritme til at bestemme komposit.
for at løse dit sidste spørgsmål skal vi indføre reduktion. Reduktioner er et meget stærkt begreb teoretisk datalogi. At reducere et problem til et andet betyder grundlæggende at løse et problem ved at løse et andet problem.
lad Lira være et alfabet og A og B være Sprog over Lira. A er polynomisk-tid mange-en reducerbar til B, hvis der findes en funktion f: lodret med følgende egenskaber.
- v kr A Kr f(V) kr b for alle v kr.
- funktionen f kan beregnes af en Turing-maskine for hver indgang i et antal trin afgrænset af et polynom i |m|.
i dette tilfælde skriver vi en kur p B.
lad f.eks. være det sprog, der indeholder alle grafer (kodet som adjacency matrice), der indeholder en trekant. (En trekant er en cyklus af længde 3.) Lad yderligere B være det sprog, der indeholder alle matricer med ikke-nul spor. (Sporet af en matrice er summen af dets vigtigste diagonale elementer.) Så er a polynomisk tid mange-en reducerbar til B. For at bevise dette skal vi finde en passende transformationsfunktion f. i dette tilfælde kan vi indstille f til at beregne 3.effekt af adjacency matricen. Dette kræver to matrice-matrice produkter, som hver har polynomisk kompleksitet.
det er trivielt sandt, at l Kurt p L. (kan du bevise det formelt?)
Vi anvender dette på NP nu.
et sprog L er NP-hårdt, hvis og kun hvis L’ Purp p l for hvert sprog L’ Purpur NP.
et NP-hårdt sprog kan eller måske ikke være i NP selv.
et sprog L er NP-komplet, hvis og kun hvis
- l er NP-hårdt.
det mest berømte NP-komplette sprog er SAT. Den indeholder alle boolske formler, der kan opfyldes. For eksempel, (A kr.b) kr. (a kr. B) kr. kr. Et gyldigt vidne er {a = 1, b = 0}. Formlen (a ∨ b) ∧ (a ∨ b) ∧ b ∉ SAD. (Hvordan ville du bevise det?)
det er ikke svært at vise, at lør lør NP. At vise NP-hårdheden af SAT er noget arbejde, men det blev udført i 1971 af Stephen Cook.
Når det ene NP-komplette sprog var kendt, var det relativt enkelt at vise NP-fuldstændigheden af andre sprog via reduktion. Hvis Sprog A er kendt for at være NP-hårdt, så viser det, at en purpur p b viser, at B også er NP-hårdt (via transitiviteten af “purpur p”). I 1972 Richard Karp offentliggjort en liste over 21 sprog, som han kunne vise var NP-komplet via (transitiv) reduktion af SAT. (Dette er det eneste papir i dette svar, som jeg faktisk anbefaler, at du skal læse. I modsætning til de andre, det er ikke svært at forstå og giver en meget god ide om, hvordan bevise NP-fuldstændighed via reduktion værker.)
endelig en kort oversigt. Vi bruger symbolerne NPH og NPC til at betegne klasserne af henholdsvis NP-hard og NP-complete sprog.
- P&delmængde; NP
- NPC & delmængde; NP og NPC &delmængde; NPH, faktisk NPC = NP ∩ NPH-definition
- (A ∈ NP) ∧ B ∈ NPH) ⇒ A ≤p B
Bemærk, at optagelse NPC &delmængde; NP er korrekt, selv i tilfælde af, at P = NP. For at se dette skal du gøre dig klar over, at intet ikke-trivielt sprog kan reduceres til et trivielt sprog, og der er trivielle sprog på P såvel som ikke-trivielle sprog i NP. Dette er dog en (ikke særlig interessant) hjørnesag.
din primære kilde til forvirring ser ud til at være, at du tænkte på “n” I “O(N kur f(n))” som fortolkningen af en algoritmes input, når den faktisk refererer til længden af input. Dette er en vigtig skelnen, fordi det betyder, at den asymptotiske kompleksitet af en algoritme afhænger af den kodning, der bruges til input.
denne uge blev der opnået en ny rekord for den største kendte Mersenne prime. Det største kendte primtal er 274 207 281 − 1. Dette tal er så stort, at det giver mig hovedpine, så jeg bruger en mindre i følgende eksempel: 231 – 1 = 2 147 483 647. Det kan kodes på forskellige måder.
- ved sin Mersenne-eksponent som decimaltal:
31(2 bytes) - som decimaltal:
2147483647(10 bytes) - som unary number:
11111…11hvor…skal erstattes af 2 147 483 640 mere1s (næsten 2 GiB)
alle disse strenge koder for det samme nummer og givet nogen af disse, kan vi let konstruere enhver anden kodning af det samme nummer. (Du kan erstatte decimalkodning med binær, oktal eller seksadecimal, hvis du vil. Det ændrer kun længden med en konstant faktor.)
den naive algoritme til test af primalitet er kun polynom for unære kodninger. AKS-primalitetstesten er polynom for decimal (eller en hvilken som helst anden base B-2). Lucas-Lehmer primalitetstest er den bedst kendte algoritme for Mersenne primes Mp med p en ulige prime, men den er stadig eksponentiel i længden af den binære kodning af Mersenne-eksponenten p (polynom i p).
hvis vi vil tale om kompleksiteten af en algoritme, er det meget vigtigt, at vi er meget klare, hvilken repræsentation vi bruger. Generelt kan man antage, at den mest effektive kodning anvendes. Det vil sige binært for heltal. (Bemærk, at ikke alle primtal er en Mersenne prime, så brug af Mersenne-eksponenten er ikke et generelt kodningsskema.)
i teoretisk kryptografi er mange algoritmer formelt bestået en helt ubrugelig streng af k 1 s som den første parameter. Algoritmen ser aldrig på denne parameter, men den gør det muligt for den formelt at være polynom i k, som er sikkerhedsparameteren, der bruges til at indstille procedurens sikkerhed.
for nogle problemer, hvor beslutningssproget i binær kodning er NP-komplet, er beslutningssproget ikke længere NP-komplet, hvis kodningen af indlejrede tal skiftes til unary. Beslutningssprogene for andre problemer forbliver NP-komplette selv da. Sidstnævnte kaldes stærkt NP-komplet. Det bedst kendte eksempel er bin pakning.
det er også (og måske mere) interessant at se, hvordan kompleksiteten af en algoritme ændres, hvis input komprimeres. For eksemplet med Mersenne primes har vi set tre kodninger, som hver er logaritmisk mere komprimeret end sin forgænger.
i 1983 har Hana Galperin og Avi Vigderson skrevet et interessant papir om kompleksiteten af almindelige grafalgoritmer, når inputkodningen af grafen komprimeres logaritmisk. For disse indgange bliver sproget af grafer indeholdende en trekant ovenfra (hvor det tydeligt var i P) pludselig NP-komplet.
og det er fordi sprogklasser som P og NP er defineret for sprog, ikke for problemer.