försöker förstå P vs NP vs NP Complete vs NP Hard

det första att förstå är att P och NP klassificera språk, inte problem. För att förstå vad detta betyder behöver vi några andra definitioner först.

ett alfabet är en icke-tom ändlig uppsättning symboler.

{01} är ett alfabet liksom ASCII-teckenuppsättningen. {} är inte ett alfabet eftersom det är tomt. N (heltal) är inte ett alfabet eftersom det inte är ändligt.

låt det vara ett alfabet. En ordnad sammanfogning av ett begränsat antal symboler från Kuban kallas ett ord över Kuban.

strängen101 är ett ord över alfabetet {01}. Det tomma ordet (ofta skrivet som kub) är ett ord över vilket alfabet som helst. Strängen penguin är ett ord över alfabetet som innehåller ASCII-tecknen. Decimalbeteckningen för numret Kubi är inte ett ord över alfabetet {.0123456789} eftersom det inte är ändligt.

längden på ett ord w, skrivet som |w|, är antalet symboler i det.

till exempel, |hello| = 5 och |ACI| = 0. För vilket ord som helst w, |w| kub N och därför ändlig.

låt det vara ett alfabet. Satsen innehåller alla ord över den, inklusive den. Satsen innehåller alla ord över den, utom den. För n av n av n av N är av n av den uppsättning av ord av längd n.

för varje alfabet är av den oändliga räknbara uppsättningen. För ASCII-teckenuppsättningen ASICASCII betecknar reguljära uttryck .* och .+ respektive.

{01}7 är uppsättningen 7-bitars ASCII-koder {00000000000001111111101} 32 är uppsättningen av 32 bitars heltal värden.

låt det vara ett alfabet och L⊆ L kallas ett språk över Aug.

för ett alfabet, är den tomma uppsättningen och Kuban triviala språk över Kuban. Den förra kallas ofta det tomma språket. Det tomma språket {} och det språk som endast innehåller det tomma ordet {Kubi} är olika.

delmängden av {01}32 som motsvarar icke-NaN IEEE 754 flyttalsvärden är ett ändligt språk.

språk kan ha ett oändligt antal ord men varje språk kan räknas. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Den oändliga uppsättningen strängar {23571113, …} betecknar primtal i decimal notation är en riktig delmängd därav. Språket som innehåller alla ord som matchar det reguljära uttrycket ?\d+\.\d*(?\d+)? är ett språk över ASCII-teckenuppsättningen (betecknar en delmängd av de giltiga flytpunktsuttrycken som definieras av programmeringsspråket C).

det finns inget språk som innehåller alla reella tal (i någon notation) eftersom uppsättningen reella tal inte kan räknas.

låt det vara ett alfabet och L⊆ En maskin d bestämmer L om för varje inmatning w ∈ den beräknar den karakteristiska funktionen XL(w) i ändlig tid. Den karakteristiska funktionen definieras som

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

en sådan maskin kallas en decider För L. vi skriver” D(w) = x ”för”givet w, D utgångar x”.

det finns många maskinmodeller. Den mest allmänna som används praktiskt idag är modellen för en Turing-maskin. En Turing-maskin har obegränsad linjär Lagring grupperad i celler. Varje cell kan hålla exakt en symbol för ett alfabet när som helst. Turing-maskinen utför sin beräkning som en sekvens av beräkningssteg. I varje steg kan den Läsa en cell, eventuellt skriva över dess värde och flytta läs – /skrivhuvudet med en position till vänster eller höger cell. Vilken åtgärd maskinen ska utföra styrs av en ändlig tillståndsautomat.

en slumpmässig åtkomstmaskin med en begränsad uppsättning instruktioner och obegränsad lagring är en annan maskinmodell som är lika kraftfull som Turing-maskinmodellen.

För denna diskussion ska vi inte störa oss med den exakta maskinmodellen vi använder utan snarare tillräckligt för att säga att maskinen har en ändlig deterministisk styrenhet, obegränsad lagring och utför en beräkning som en sekvens av steg som kan räknas.

eftersom du har använt det i din fråga antar jag att du redan är bekant med ”big-O” notation så här är bara en snabb uppdatering.

låt f: n IC vara en funktion. Setet O(f) innehåller alla funktioner g: n.n. n. n. för vilka det finns konstanter n0. n. n. n. och c. n. n. så att för varje n. n. n. n. n. n. n. n. n. n. n. n. n. n. n. n. n. n. n. n.

Nu är vi beredda att närma oss den verkliga frågan.

klassen P innehåller alla språk L för vilka det finns en Turing-maskin D som bestämmer L och en konstant k kubi n så att för varje ingång W, D stannar efter högst t (|w/) steg för en funktion t Michai O(n michai nk).

eftersom o(n Audrey nk), medan matematiskt korrekt, är obekvämt att skriva och läsa, skriver de flesta – för att vara ärlig, alla utom mig själv – vanligtvis helt enkelt O(nk).

Observera att bindningen beror på längden på w. därför är argumentet du gör för primernas språk endast korrekt för siffror i unaray-kodningar, där kodningen w för ett tal n är längden på kodningen |w| proportionell mot n.ingen skulle någonsin använda en sådan kodning i praktiken. Med hjälp av en mer avancerad algoritm än att bara försöka alla möjliga faktorer kan det dock visas att primtalsspråket förblir i P om ingångarna är kodade i binär (eller till någon annan bas). (Trots massivt intresse kunde detta bara bevisas av Manindra Agrawal, Neeraj Kayal och Nitin Saxena i ett prisbelönt papper 2004 så att du kan gissa att algoritmen inte är så enkel.)

de triviala språken {} och Kubi och det icke-triviala språket {kubi} är uppenbarligen i P (för vilket alfabet som helst). Kan du skriva funktioner i ditt favoritprogrammeringsspråk som tar en sträng som inmatning och returnera en boolesk som berättar om strängen är ett ord från språket för var och en av dessa och bevisa att din funktion har polynomisk körtidskomplexitet?

varje vanligt språk (ett språk som beskrivs av ett reguljärt uttryck) finns i P.

låt det vara ett alfabet och L⊆. En maskin V som tar en kodad tupel av två ord w, c kubi och matar ut 0 eller 1 efter ett begränsat antal steg är en verifierare för L om den har följande egenskaper.

• givet (w, c), v-utgångar 1 endast om wmic L.
• för varje wmic l finns det en CMIC sådan att v(w, c) = 1.

c i ovanstående definition kallas ett vittne (eller certifikat).

en verifierare får ge falska negativ för fel vittne även om w faktiskt är i L. Det är dock inte tillåtet att ge falska positiva. Det krävs också att för varje ord på språket finns det minst ett vittne.

För SPRÅKKOMPOSITEN, som innehåller decimalkodningarna för alla heltal som inte är primära, kan ett vittne vara en faktorisering. Till exempel, (659, 709) är ett vittne för 467231 Jacobs komposit. Du kan enkelt verifiera att på ett pappersark utan att vittnet ges, vilket bevisar att 467231 inte är prime skulle vara svårt utan att använda en dator.

vi sa ingenting om hur ett lämpligt vittne kan hittas. Detta är den icke-deterministiska delen.

klassen NP innehåller alla språk L för vilka det finns en Turing-maskin V som verifierar L och en konstant k kubi n så att för varje ingång (w, c), v stannar efter högst t (|w/) steg för en funktion t Michai O(n michai nk).

Observera att ovanstående definition innebär att för varje w CCR L finns ett vittne C med |C| CCR T(|w|). (Turing-maskinen kan omöjligt titta på Fler symboler för vittnet.)

NP är en superset av P (varför?). Det är inte känt om det finns språk som finns i NP men inte I P.

Heltalsfaktorisering är inte ett språk i sig. Vi kan dock konstruera ett språk som representerar beslutsproblemet i samband med det. Det vill säga ett språk som innehåller alla tuplar (n, m) så att n har en faktor d med d ≤ m. låt oss kalla denna språkfaktor. Om du har en algoritm för att bestämma faktor, det kan användas för att beräkna en fullständig faktorisering med endast polynom overhead genom att utföra en rekursiv binär sökning för varje primfaktor.

det är lätt att visa att faktorn är i NP. Ett lämpligt vittne skulle helt enkelt vara faktorn d själv och allt verifieraren skulle behöva göra är att verifiera att d ≤ m och n mod d = 0. Allt detta kan göras i polynom tid. (Kom ihåg, igen, att det är längden på kodningen som räknas och det är logaritmiskt i n.)

Om du kan visa att faktorn också finns i P, kan du vara säker på att få många coola utmärkelser. (Och du har brutit en betydande del av dagens kryptografi.)

För varje språk i NP finns det en brute-force-algoritm som bestämmer den deterministiskt. Det utför helt enkelt en uttömmande sökning över alla vittnen. (Observera att ett vittnes maximala längd begränsas av ett polynom.) Så, din algoritm för att bestämma PRIMES var faktiskt en brute-force algoritm för att bestämma komposit.

för att ta itu med din sista fråga måste vi införa reduktion. Minskningar är ett mycket kraftfullt begrepp teoretisk datavetenskap. Att minska ett problem till ett annat innebär i princip att lösa ett problem genom att lösa ett annat problem.

låt Kuban vara ett alfabet och A och B vara Språk över Kuban. A är polynomial-time många-en reducerbar till B om det finns en funktion f: megapixlar med följande egenskaper.

• w oc A oc f(w) oc B för alla oc oc.
• funktionen f kan beräknas av en Turing-maskin för varje ingång w i ett antal steg avgränsade av ett polynom i |w|.

i det här fallet skriver vi en kubi p B.

låt till exempel A vara det språk som innehåller alla grafer (kodade som adjacency matrix) som innehåller en triangel. (En triangel är en cykel med Längd 3.) Låt ytterligare B vara det språk som innehåller alla matriser med icke-noll spår. (Spåret av en matris är summan av dess huvudsakliga diagonala element.) Då är A polynomtid många-en reducerbar till B. För att bevisa detta måste vi hitta en lämplig transformationsfunktion f. i det här fallet kan vi ställa in f för att beräkna den 3: e kraften i adjacency-matrisen. Detta kräver två matrismatrisprodukter, som var och en har polynomkomplexitet.

det är trivialt sant att l bisexuell p L. (kan du bevisa det formellt?)

Vi tillämpar detta på NP nu.

ett språk L är NP-hårt om och endast om l’ kubi p L för varje språk l’ Kubi NP.

ett NP-hårt språk kan eller kanske inte vara i NP själv.

ett språk L är NP-komplett om och endast om

• l NP och
• L är NP-hård.

det mest kända NP-kompletta språket är SAT. Den innehåller alla booleska formler som kan uppfyllas. Till exempel, (en B) B) B) SAT. Ett giltigt vittne är {A = 1, b = 0}. Formeln (A B) B B B SAT. (Hur skulle du bevisa det?)

det är inte svårt att visa att SAT Bisexuell NP. Att visa NP-hårdheten hos SAT är lite arbete men det gjordes 1971 av Stephen Cook.

När ett NP-komplett språk var känt var det relativt enkelt att visa NP-fullständigheten hos andra språk via reduktion. Om språk a är känt för att vara NP-hårt, visar det att en kub p B visar att B är NP-hård också (via transitiviteten av ”kub p”). 1972 publicerade Richard Karp en lista över 21 språk som han kunde visa var NP-komplett via (transitiv) reduktion av SAT. (Detta är det enda papperet i det här svaret som jag faktiskt rekommenderar att du borde läsa. Till skillnad från de andra är det inte svårt att förstå och ger en mycket bra uppfattning om hur bevisande NP-fullständighet via reduktion fungerar.)

slutligen en kort sammanfattning. Vi använder symbolerna NPH och NPC för att beteckna klasserna av NP-hårda respektive NP-kompletta språk.

• P ⊆ NP
• NPC &delmängd; NP och NPC &delmängd; NPH, faktiskt NPC = NP ∩ NPH av definitionen
• A ∈ NP) ∧ (B ∈ NPH) ⇒ A ≤p B

Observera att införandet NPC &delmängd, NP är rätt även i det fall att P = NP. För att se detta, gör dig klar att inget icke-trivialt språk kan reduceras till ett trivialt språk och det finns triviala språk på P såväl som icke-triviala språk i NP. Detta är dock ett (inte särskilt intressant) hörnfall.

din primära källa till förvirring verkar vara att du tänkte på ”n” I ”O(n kubi f(n))” som tolkningen av en algoritms inmatning när den faktiskt hänvisar till inmatningens längd. Detta är en viktig skillnad eftersom det betyder att den asymptotiska komplexiteten hos en algoritm beror på kodningen som används för ingången.

den här veckan uppnåddes en ny rekord för den största kända Mersenne prime. Det största för närvarande kända primtalet är 274 207 281 − 1. Detta nummer är så stort att det ger mig huvudvärk så jag använder en mindre i följande exempel: 231 – 1 = 2 147 483 647. Det kan kodas på olika sätt.

• med sin Mersenne exponent som decimaltal: 31 (2 byte)
• som decimaltal: 2147483647 (10 byte)
• som unary tal: 11111…11 där … ska ersättas med 2 147 483 640 mer 1s (nästan 2 gib)

alla dessa strängar kodar för samma nummer och med någon av dessa kan vi enkelt konstruera någon annan kodning av samma nummer. (Du kan ersätta decimalkodning med binär, oktal eller hexadecimal om du vill. Det ändrar bara längden med en konstant faktor.)

den naiva algoritmen för att testa primalitet är endast polynom för unära kodningar. AKS – primalitetstestet är polynom för decimal (eller någon annan bas b kubi 2). Lucas-Lehmer primality test är den mest kända algoritmen för Mersenne primes Mp med p en udda prime men det är fortfarande exponentiellt i längden på den binära kodningen av Mersenne exponent p (polynom i p).

Om vi vill prata om komplexiteten hos en algoritm är det mycket viktigt att vi är mycket tydliga vilken representation vi använder. I allmänhet kan man anta att den mest effektiva kodningen används. Det vill säga binärt för heltal. (Observera att inte varje primtal är en Mersenne prime så att använda Mersenne exponent är inte ett allmänt kodningsschema.)

i teoretisk kryptografi skickas många algoritmer formellt en helt värdelös sträng av k 1 s som den första parametern. Algoritmen tittar aldrig på denna parameter men det gör det möjligt att formellt vara polynom i k, vilket är säkerhetsparametern som används för att ställa in procedurens säkerhet.

För vissa problem för vilka beslutsspråket i binär kodning är NP-complete är beslutsspråket inte längre NP-complete om kodningen av inbäddade nummer byts till unary. Beslutsspråken för andra problem förblir NP-kompletta även då. De senare kallas starkt NP-komplett. Det mest kända exemplet är bin packning.

det är också (och kanske mer) intressant att se hur komplexiteten hos en algoritm ändras om ingången komprimeras. För exemplet med Mersenne-primtal har vi sett tre kodningar, som var och en är logaritmiskt mer komprimerade än föregångaren.

1983 har Hana Galperin och Avi Wigderson skrivit ett intressant papper om komplexiteten hos vanliga grafalgoritmer när inmatningskodningen av grafen komprimeras logaritmiskt. För dessa ingångar blir språket för grafer som innehåller en triangel ovanifrån (där det tydligt var i P) plötsligt NP-komplett.

och det beror på att språkklasser som P och NP definieras för språk, inte för problem.