Det første du må forstå er At P og NP klassifiserer språk, ikke problemer. For å forstå hva dette betyr, trenger vi noen andre definisjoner først.
et alfabet er et ikke-tomt, endelig sett med symboler.
{01} er et alfabet som ascii-tegnsettet. {} er ikke et alfabet fordi det er tomt. N (heltallene) er ikke et alfabet fordi det ikke er endelig.
La Σ være et alfabet. En ordnet sammenkobling av et begrenset antall symboler fra Σ kalles et ord over Σ.
strengen101 er et ord over alfabetet {01}. Det tomme ordet (ofte skrevet som ε) er et ord over et hvilket som helst alfabet. Strengen penguin er et ord over alfabetet som inneholder ASCII-tegnene. Desimalnotasjonen til tallet π er ikke et ord over alfabetet {.0123456789} fordi den ikke er endelig.
lengden på et ord w, skrevet som / w/ , er antall symboler i den.
For eksempel,/hello / = 5 og |ε| = 0. For ethvert ord w, / w / ∈ N og derfor endelig.
La Σ være et alfabet. Det innstilte Σ ＊ inneholder alle ord over σ, inkludert ε Alle ord som er satt til Σ+ inneholder alle ord over Σ, unntatt ε. For n ∈ N er Σ et sett med ord med lengde n.
for hvert Alfabet Σ, Σ ＊ Og σ+ er uendelige tellbare sett. For ASCII-tegnsettet Σ vil regulære uttrykk .* og .+ BETEGNE HRYVASCII＊ og Σ+ henholdsvis.
{01}7 er settet med 7-biters ASCII-koder {00000000000001111111101} 32 er settet med 32 bit heltallsverdier.
La Σ være et alfabet og L &Subseteq; Σ ＊. L kalles et språk over Σ.
for et alfabet Σ er det tomme settet og Σ ＊ trivielle språk over σ. Den førstnevnte blir ofte referert til som det tomme språket. Det tomme språket {} og språket som bare inneholder det tomme ordet {ε} er forskjellige.
delsettet av {01}32 som tilsvarer ikke-nan ieee 754 flyttallsverdier er et endelig språk.
Språk kan ha et uendelig antall ord, men hvert språk kan telles. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Det uendelige settet med strenger {23571113, …} betegner primtallene i desimalnotasjon er en riktig delmengde derav. Språket som inneholder alle ord som samsvarer med det regulære uttrykket ?\d+\.\d*(?\d+)? er et språk over ASCII-tegnsettet(angir et delsett av de gyldige flyttallsuttrykkene som definert Av c-programmeringsspråket).
det er ikke noe språk som inneholder alle reelle tall (i noen notasjon) fordi settet med reelle tall ikke kan telles.
La Σ være et alfabet og L &Subseteq; Σ ＊. En maskin d bestemmer L hvis for hver inngang w & i; Σ ＊ beregner den karakteristiske funksjonen xl(w) i begrenset tid. Den karakteristiske funksjonen er definert som
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.en slik maskin kalles en bestemmer For L. vi skriver «D (w) = x» for «gitt w, D utganger x».
det er mange maskinmodeller. Den mest generelle som er i praktisk bruk i dag, er modellen Til En Turing-maskin. En Turing maskin har ubegrenset lineær lagring gruppert i celler. Hver celle kan holde nøyaktig ett symbol på et alfabet til enhver tid. Turing-maskinen utfører sin beregning som en sekvens av beregningstrinn. I hvert trinn kan det lese en celle, muligens overskrive verdien og flytte lese / skrivehodet med en posisjon til venstre eller høyre celle. Hvilken handling maskinen skal utføre styres av en endelig tilstandsautomat.en tilfeldig tilgangsmaskin med et begrenset sett med instruksjoner og ubegrenset lagring er en annen maskinmodell som er like kraftig Som Turing-maskinmodellen.for denne diskusjonens skyld skal vi ikke bry oss med den nøyaktige maskinmodellen vi bruker, men heller nok til å si at maskinen har en endelig deterministisk kontrollenhet, ubegrenset lagring og utfører en beregning som en sekvens av trinn som kan telles.Siden du har brukt det I spørsmålet ditt, antar jeg at du allerede er kjent med» big-O » notasjon, så her er bare en rask oppfriskning.
La f: N → være en funksjon. Settet O (f) inneholder alle funksjoner g: N → N for hvilke det finnes konstanter n0 ∈ N Og c ∈ N slik at for hver n ∈ N med n > n0 er det sant at g(n) ≤ c f (n).
nå er Vi forberedt på å nærme seg det virkelige spørsmålet.
klassen P inneholder alle språk L Der Det finnes En Turing maskin D som bestemmer L og en konstant k ∈ n Slik at for hver inngang w, d stopper etter på de fleste t (|w/) trinn For en funksjon T ∈ O (n ↦ nk).
Siden O(n ↦ nk), mens matematisk korrekt, er ubeleilig å skrive Og lese, skriver de fleste – for å være ærlig, alle unntatt meg selv – vanligvis Bare O(nk).
Merk at bundet avhenger av lengden på w. derfor er argumentet du lager for primtallets språk bare riktig for tall i unaray-kodinger, hvor for kodingen w av et tall n, er lengden på kodingen| w / proporsjonal med n.Ingen ville noen gang bruke en slik koding i praksis. Ved å bruke en mer avansert algoritme enn bare å prøve alle mulige faktorer, kan det imidlertid vises at språket av primtall forblir I P hvis inngangene er kodet i binær (eller til en annen base). (Til tross for massiv interesse, kan dette bare bevises Av Manindra Agrawal, Neeraj Kayal og Nitin Saxena i et prisbelønt papir i 2004, slik at du kan gjette at algoritmen ikke er veldig enkel.)
de trivielle språkene {} og Σ ＊ og det ikke-trivielle språket {} er åpenbart i p (for alle alfabetiske σ). Kan du skrive funksjoner i ditt favorittprogrammeringsspråk som tar en streng som inngang og returnerer en boolsk som forteller om strengen er et ord fra språket for hver av disse og bevise at funksjonen din har polynomisk kjøretidskompleksitet?
hvert vanlig språk (et språk som beskrives med et regulært uttrykk) er I P.
La Σ være et alfabet og L &Subseteq; Σ ＊. En maskin V som tar en kodet tuple av to ord w, c ∈ σ ＊ og utganger 0 eller 1 etter et begrenset antall trinn er en verifikator for l hvis den har følgende egenskaper.
- Gitt (w, c), v utganger 1 bare hvis w ∈ L.
- for hver w ∈ L finnes det en c ∈ σ ＊ Slik at v(W, c) = 1.
c i definisjonen ovenfor kalles et vitne (eller sertifikat).
en verifikator har lov til å gi falske negativer for feil vitne selv om w faktisk er I L. det er imidlertid ikke tillatt å gi falske positiver. Det kreves også at for hvert ord på språket finnes det minst ett vitne.
for SPRÅKKOMPOSITTEN, som inneholder desimalkodingene av alle heltall som ikke er primtall, kan et vitne være en faktorisering. For eksempel er (659, 709)et vitne for 467231 ∈ SAMMENSATT. Du kan enkelt kontrollere at på et ark mens uten vitne gitt, beviser at 467231 er ikke prime ville være vanskelig uten å bruke en datamaskin.
Vi sa ikke noe om hvordan et passende vitne kan bli funnet. Dette er den ikke-deterministiske delen.
klassen NP inneholder alle språk L For hvilke Det finnes En Turing maskin V som verifiserer L og en konstant k ∈ N Slik at For hver inngang (w, c) stopper V etter maksimalt t (|w/) trinn For en funksjon T ∈ O (n ↦ nk).
Merk at definisjonen ovenfor innebærer at for hver w ∈ l finnes det et vitne c med / c / ≤ T (|w/). (Turingmaskinen kan umulig se på flere symboler av vitnet.)
NP ER et supersett Av P (hvorfor?). Det er ikke kjent om det finnes språk som er I NP, men ikke I P.
Heltallsfaktorisering er ikke et språk i seg selv. Vi kan imidlertid konstruere et språk som representerer beslutningsproblemet knyttet til det. Det vil si et språk som inneholder alle tuples (n, m) slik at n har en faktor d med d ≤ m. la oss kalle denne språkfaktoren. Hvis du har en algoritme for å bestemme FAKTOR, kan DEN brukes til å beregne en full faktorisering med bare polynomisk overhead ved å utføre et rekursivt binært søk for hver primærfaktor.
det er lett å vise AT FAKTOREN er I NP. Et passende vitne ville ganske enkelt være faktoren d selv, og alt verifikatoren måtte gjøre er å verifisere at d & leq; m og n mod d = 0. Alt dette kan gjøres i polynomisk tid. (Husk igjen at det er lengden på kodingen som teller og det er logaritmisk i n.)
Hvis DU kan vise AT FAKTOREN også er I P, kan du være sikker på å få mange kule priser. (Og du har brutt en betydelig del av dagens kryptografi.)
for hvert språk I NP er det en brute-force algoritme som bestemmer det deterministisk. Det utfører bare et uttømmende søk over alle vitner. (Merk at maksimal lengde på et vitne er begrenset av et polynom. Så algoritmen din for å bestemme PRIMTALL var faktisk en brute-force algoritme for å bestemme KOMPOSITT.
for å løse ditt siste spørsmål, må vi innføre reduksjon. Reduksjoner er et veldig kraftig konsept for teoretisk datavitenskap. Å redusere et problem til et annet betyr i utgangspunktet å løse ett problem ved å løse et annet problem.
La Σ være et alfabet og A og B være språk over Σ. A er polynomisk tid mange-en reduserbar Til B hvis det finnes en funksjon f: Σ ＊ → σ ＊ Med følgende egenskaper.
- w ∈ en ⇔ f (w) ∈
- funksjonen f kan beregnes av En Turing maskin for hver inngang w i en rekke trinn avgrenset av et polynom i / w/.
i dette tilfellet skriver vi en ≤p B.
la For eksempel a være språket som inneholder alle grafer (kodet som adjacency matrix) som inneholder en trekant. (En trekant er en syklus av lengde 3.) La videre b v re spraket som inneholder alle matriser med ikke-nullspor. (Sporet av en matrise er summen av de viktigste diagonale elementene.) Da er a polynomisk tid mange-en reduserbar Til B. For å bevise dette må vi finne en passende transformasjonsfunksjon f.I dette tilfellet kan vi sette f for å beregne 3rd-kraften til adjacency-matrisen. Dette krever to matrise-matriseprodukter, som hver har polynomisk kompleksitet.
det er trivielt sant At l ≤p L. (Kan du bevise det formelt?)
vi bruker DETTE til NP nå.
et språk L er NP-hardt hvis og bare Hvis l’ ≤p l for hvert språk L’ ∈ NP.
et np-hardt språk kan eller ikke kan være I NP selv.
et språk L er np-komplett hvis og bare hvis
- L ∈ NP og
- L er np-hard.
DET mest kjente np-komplette språket ER SAT. Den inneholder alle boolske formler som kan tilfredsstilles. For eksempel, (en ∨ b) ∧ Et gyldig vitne er {a = 1, b = 0}. Formelen(en ∨ b) ∧ (Hvordan ville du bevise det?)
DET er ikke vanskelig å vise AT SAT ∈ NP. Å vise NP-hardheten TIL SAT er noe arbeid, men Det ble gjort I 1971 Av Stephen Cook.
Når det ENE np-komplette språket var kjent, var det relativt enkelt å vise np-fullstendigheten til andre språk via reduksjon. Hvis språk A er KJENT FOR Å VÆRE NP-hard, viser det at en ≤p B viser At B ER NP-hard også(via transittiviteten til «≤p»). I 1972 publiserte Richard Karp en liste over 21 språk som Han kunne vise VAR NP-komplett via (transitiv) reduksjon AV SAT. (Dette er det eneste papiret i dette svaret som jeg faktisk anbefaler at du bør lese. I motsetning til de andre er det ikke vanskelig å forstå og gir en veldig god ide om hvordan å bevise np-fullstendighet via reduksjon fungerer.)
Endelig en kort oppsummering. Vi bruker symbolene NPH og NPC for å betegne klassene AV HENHOLDSVIS np-hard og np-complete språk.
- P&delmengde; NP
- NPC & delmengde; NP og NPC &delsett; NPH, faktisk NPC = NP ∩ NPH per definisjon
- (A ∈ NP) ∧ (B ∈ NPH) ⇒ A ≤p B
Merk at inkludering NPC &delsett; NP er riktig selv i tilfelle at P = NP. For å se dette, gjør deg klar over at ingen ikke-trivielle språk kan reduseres til en triviell, og det er trivielle språk i P så vel som ikke-trivielle språk i NP. Dette er en (ikke veldig interessant) hjørnesak, skjønt.din primære kilde til forvirring ser ut til å være at du tenkte på «n» i «O(n ↦ f(n))» som tolkningen av en algoritmes inngang når den faktisk refererer til lengden på inngangen. Dette er et viktig skille fordi det betyr at asymptotisk kompleksitet av en algoritme avhenger av kodingen som brukes til inngangen.
Denne uken ble en ny rekord for den største kjente mersenne prime oppnådd. Det største kjente primtallet er 274 207 281 − 1. Dette nummeret er så stort at det gir meg hodepine, så jeg bruker en mindre i følgende eksempel: 231 – 1 = 2 147 483 647. Den kan kodes på forskjellige måter.
- ved Sin mersenne eksponent som desimalnummer:
31(2 byte) - som desimalnummer:
2147483647(10 byte) - som unært tall:
11111…11hvor…skal erstattes av 2 147 483 640 mer1s (nesten 2 gib)
alle disse strengene koder det samme nummeret og gitt noen av disse, kan vi enkelt konstruere noen annen koding av samme nummer. (Du kan erstatte desimalkoding med binær, oktal eller heksadesimal hvis du vil. Det endrer bare lengden med en konstant faktor.)
den naive algoritmen for testing av primalitet er bare polynom for unære kodinger. AKS primalitetstesten er polynom for desimal (eller annen base b ≥ 2). Lucas-Lehmer primality test er den mest kjente algoritmen For Mersenne primtall Mp med p en merkelig primtall, men det er fortsatt eksponentiell i lengden av den binære koding Av Mersenne eksponenten p (polynom i p).
hvis vi vil snakke om kompleksiteten til en algoritme, er det svært viktig at vi er veldig klare hvilken representasjon vi bruker. Generelt kan man anta at den mest effektive kodingen brukes. Det er binært for heltall. (Merk at ikke alle primtall er En mersenne prime, så bruk Av mersenne-eksponenten er ikke et generelt kodingssystem.)
i teoretisk kryptografi er mange algoritmer formelt bestått en helt ubrukelig streng av k 1 s som den første parameteren. Algoritmen ser aldri på denne parameteren, men det tillater det å formelt være polynom i k, som er sikkerhetsparameteren som brukes til å justere sikkerheten til prosedyren.
for noen problemer der beslutningsspråket i binær koding ER np-komplett, er beslutningsspråket ikke lenger np-komplett hvis kodingen av innebygde tall blir byttet til unary. Beslutningsspråkene for andre problemer forblir NP-komplette selv da. Sistnevnte kalles sterkt NP-komplett. Det mest kjente eksemplet er bin pakking.
Det er også (og kanskje mer) interessant å se hvordan kompleksiteten til en algoritme endres hvis inngangen komprimeres. For eksempel Mersenne primtall, har vi sett tre kodinger, som hver er logaritmisk mer komprimert enn forgjengeren.I 1983 har Hana Galperin og Avi Wigderson skrevet et interessant papir om kompleksiteten til vanlige grafalgoritmer når inngangskodingen av grafen komprimeres logaritmisk. For disse inngangene blir språket i grafer som inneholder en trekant ovenfra (hvor det var tydelig I P) plutselig NP-komplett.
og det er fordi språkklasser Som P og NP er definert for språk, ikke for problemer.