Svar

Svar

Svar

,1,2,3,4,5,6,7,8,9}. Den oändliga stränguppsättningen {2,3,5,7,11,13, …} som anger primtal i decimalnotation är en korrekt delmängd därav. Språket som innehåller alla ord som matchar det reguljära uttrycket[+-]?\d+\.\d*([eE][+-]?\d+)?är ett språk över ASCII-teckenuppsättningen (betecknar en delmängd av de giltiga flytpunktsuttrycken som definierats av C-programmeringsspråket).

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

Låt Σ vara ett alfabet och L ⊆ Σ ^＊ . En maskin D bestämmer L om för varje ingång w ∈ Σ ^＊ den beräknar karakteristisk funktion χ _L ( w ) på begränsad tid. Den karakteristiska funktionen definieras som

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

En sådan maskin kallas en avgörare för L . Vi skriver “ D ( w ) = x ” för ”given w , D matar ut x ”.

Det finns många maskinmodeller. Den mest allmänna som används idag är modellen för en Turingmaskin . En Turing-maskin har obegränsad linjär lagring grupperad i celler. Varje cell kan innehålla exakt en symbol i 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 kommer att utföra styrs av en slutlig automat.

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

För denna diskussions skull ska vi inte bry oss om den exakta maskinmodell vi använder utan räcker med att säga att maskinen har en ändlig deterministisk styrenhet, obegränsad lagring och utför en beräkning som en sekvens av steg det kan räknas.

Eftersom du har använt det i din fråga antar jag att du redan känner till “big-O” notation så här är bara en snabb uppdatering.

Låt f : N → vara en funktion.Uppsättningen O ( f ) innehåller alla funktioner g : N → N för vilka det finns konstanter n ₀ ∈ N och c ∈ N så att för varje n ∈ N med n > n ₀ det är sant att g ( n ) ≤ c f ( 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 ∈ N så att för varje ingång w , D stoppas efter högst T (| w |) steg för en funktion T ∈ O ( n ↦ n ^k ).

Eftersom O ( n ↦ n ^k ), även om det är matematiskt korrekt, är det obekvämt att skriva och läsa, de flesta – för att vara ärliga, alla utom jag själv – skriver vanligtvis helt enkelt O(n^k ).

Observera att gränsen beror på längden på w . Därför är argumentet du gör för primerspråket bara korrekt för siffror i unaray-kodningar , där för kodningen w av ett tal n , längden på kodningen | w | är 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 testa alla möjliga faktorer kan det dock visas att språket för primtal kvarstår i P om ingångarna är kodade i binär (eller till någon annan bas). (Trots stort 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 är inte så enkel.)

De triviala språken {} och Σ ^＊ och det icke-triviala språket { ε } finns uppenbarligen i P (för alla alfabet Σ ). Kan du skriva funktioner i ditt favoritprogrammeringsspråk som tar en sträng som inmatning och returnerar en boolean som berättar om strängen är ett ord från språket för vart och ett av dessa och bevisar att din funktion har polynomisk körtids komplexitet? p> Alla vanliga språk (ett språk som beskrivs av ett reguljärt uttryck) finns i P .

Låt Σ vara ett alfabet och L ⊆ Σ ^＊ . En maskin V som tar en kodad tuple med två ord w , c ∈ Σ ^＊ och matar ut 0 eller 1 efter ett slutligt antal steg är en verifier för L om den har följande egenskaper.

• Givet ( w , c ), V matar endast 1 om w ∈ L .
• För varje w ∈ L finns det finns en c ∈ Σ ^＊ så 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 finns i L . Det är dock inte tillåtet att ge falska positiva resultat. Det krävs också att det finns minst ett vittne för varje ord i språket.

För språket COMPOSITE, som innehåller decimalkodningarna för alla heltal som är inte primära , ett vittne kan vara en faktorisering. Till exempel är (659, 709) ett vittne för 467231 ∈ COMPOSITE. Du kan enkelt verifiera att det på ett papper utan vittnesbördet är bevisat att 467231 inte är bra utan att använda en dator.

Vi sa inget om hur ett lämpligt vittne kan vara hittades. 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 ∈ N så att för varje ingång ( w , c ), V stoppar efter högst T (| w |) steg för en funktion T ∈ O ( n ↦ n^k ).

Observera att ovanstående definition innebär att för varje w ∈ L finns ett vittne c med | c | ≤ T (| w |). (Turing-maskinen kan omöjligt titta på fler vittnesymboler.)

NP är en överuppsättning 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 som är associerat 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 detta språk FACTOR. Om du har en algoritm för att bestämma FACTOR kan den användas för att beräkna en fullständig faktorisering med endast polynomomkostnader genom att utföra en rekursiv binär sökning för varje primfaktor.

Det är lätt att visa att FACTOR ä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 på polynomtid. (Kom ihåg igen att det är längden på kodningen som räknas och att det är logaritmisk i n .)

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

För varje språk i NP finns en brute-force algoritm som bestämmer det 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 COMPOSITE.

För att ta itu med din sista fråga måste vi introducera reduktion . Reduktioner är ett mycket kraftfullt begrepp för teoretisk datavetenskap. Att reducera ett problem till ett annat innebär i grunden att lösa ett problem genom att lösa ett annat problem.

Låt Σ vara ett alfabet och A och B vara språk över Σ . A är polynomtid många-en reducerbar till B om det finns en funktion f : Σ ^＊ → Σ ^＊ med följande egenskaper.

• w ∈ A   ⇔   f ( w ) ∈ B   för alla w ∈ Σ ^＊ .
• Funktionen f kan beräknas av en Turing-maskin för varje ingång w i ett antal steg avgränsat av ett polynom i | w |.

I det här fallet skriver vi A ≤ _p B .

För låt A vara språket som innehåller alla grafer (kodade som angränsningsmatris) som innehåller en triangel. (En triangel är en cykel med längd 3.) Låt vidare B vara språket som innehåller alla matriser med spår som inte är noll. (Spårningen 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 3 ^rd -effekten för angränsningsmatrisen. Detta kräver två matrismatrisprodukter, som alla har polynomkomplexitet.

Det är triviellt sant att L ≤ _p L . (Kan du bevisa det formellt?)

Vi kommer att tillämpa detta på NP nu.

Ett språk L är NP -hard om och endast om L ”≤ _p L för varje språk L ” ∈ NP .

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

Ett språk L är NP -komplett om och bara om

• L ∈ NP och
• L är NP -hårt.

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

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

När det enda NP -kompletta språket var känt, var det relativt enkelt att visa NP -kompletten hos andra språk via reduktion. Om språket A är känt för att vara NP -hårt, visar sedan att A ≤ _p B visar att B också är NP -hårt (via transitiviteten för ”≤ _p ”). 1972 publicerade Richard Karp en lista över 21 språk som han kunde visa var NP -komplett via (transitiv) minskning av SAT. (Det här är det enda papperet i det här svaret som jag faktiskt rekommenderar att du ska läsa. Till skillnad från de andra är det inte svårt att förstå och ger en väldigt bra uppfattning om hur bevisning av NP -komplett via reduktion fungerar. )

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

• P ⊆ NP
• NPC ⊂ NP och NPC ⊂ NPH , faktiskt NPC = NP ∩ NPH per definition
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Observera att inkluderingen NPC ⊂ NP är korrekt även om P = NP . För att se detta, gör dig själv klar att inget icke-trivialt språk kan reduceras till ett trivialt språk och det finns triviala språk i P också som icke-triviala språk i NP . Thi s är dock ett (inte särskilt intressant) hörnfall.

Tillägg

Din primära källa till förvirring verkar vara att du tänkte på ” n ”i“ O ( n ↦ f ( n )) ”Som tolkning av en algoritms ingång när den faktiskt hänvisar till längden på ingången. Detta är en viktig skillnad eftersom det betyder att den asymptotiska komplexiteten hos en algoritm beror på den kodning som används för inmatningen.

Denna vecka, en ny post för den största kända Mersenne prime uppnåddes. Det största för närvarande kända primtalet är 2 ^{74   207   281} – 1. Detta tal är så stort att det ger mig huvudvärk så jag använder en mindre i följande exempel: 2 ³¹ – 1 = 2   147   483   647. Det kan kodas på olika sätt.

• av dess Mersenne-exponent som decimaltal: 31 (2 byte)
• som decimaltal: 2147483647 (10 byte)
• som unary nummer: 11111…11 där … ska ersättas med 2   147   483   640 fler 1 s (nästan 2 GiB)

Alla dessa strängar kodar samma nummer och med tanke på 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 hexadeci mal om du vill. Det ändrar bara längden med en konstant faktor.)

Den naiva algoritmen för att testa primality är endast polynom för unary kodning. AKS primality test är polynom för decimal (eller någon annan bas b ≥ 2 ). Lucas-Lehmer primality test är den mest kända algoritmen för Mersennes primtal M _p med p en udda prime men den är fortfarande exponentiell i längden på den binära kodningen av Mersenne-exponenten p (polynom i p ).

Om vi vill prata om komplexiteten i 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-exponenten inte är ett allmänt kodningsschema.)

I teoretisk kryptografi skickas många algoritmer formellt en helt värdelös sträng av k 1 är som första parameter. Algoritmen tittar aldrig på den här parametern, men den låter den formellt vara polynom i k , vilket är säkerhetsparameter 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 -komplett är beslutsspråket inte längre NP -komplett om kodningen av inbäddade nummer växlas 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 binpackning .

Det är också (och kanske mer) intressant att se hur komplexiteten hos en algoritm ändras om ingången är komprimerad . Till exempel med Mersennes primtal har vi sett tre kodningar, som var och en är logaritmiskt mer komprimerad än sin föregångare.

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

Och det ”eftersom språkklasser som P och NP definieras för språk , inte för problem .

Kommentarer

• Det här svaret är förmodligen inte användbart för förståelsens nivå. Läs de andra svaren och se vad Nanako kämpar med. Tror du det här svaret hjälper honom / henne?
• Det här svaret kanske inte hjälper OP, men hjälper verkligen andra läsare (jag själv inkluderad).
• mycket hjälpsamt svar! bör överväga att fixa matematiska symboler inte korrekt visas.

Svar