Svar

Svar

Svar

,1,2,3,4,5,6,7,8,9}. Det uendelige sæt strenge {2,3,5,7,11,13,…} der angiver primtalene i decimalnotation er en korrekt delmængde deraf. Sproget, der indeholder alle ord, der matcher det regulære udtryk[+-]?\d+\.\d*([eE][+-]?\d+)?, er et sprog over ASCII-tegnsættet (angiver et undersæt af de gyldige flydende punktudtryk som defineret af C-programmeringssproget). / p>

Der er intet sprog, der indeholder alle reelle tal (i en hvilken som helst notation), fordi sættet med reelle tal ikke kan tælles.

Lad Σ være et alfabet og L ⊆ Σ ^＊ . En maskine D beslutter L hvis for hver input w ∈ Σ ^＊ den beregner karakteristisk funktion χ _L ( w ) på endelig tid. Den karakteristiske funktion er defineret som

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

En sådan maskine kaldes en beslutningstager for L . Vi skriver “ D ( w ) = x ” for “givet w , D output x ”.

Der er mange maskinemodeller. Den mest generelle, der er praktisk anvendt i dag, er modellen til en Turing-maskine . En Turing-maskine har ubegrænset lineær lagring grupperet i celler. Hver celle kan indeholde nøjagtigt et symbol på et alfabet til enhver tid. 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 udfører styres af en endelig tilstandsautomat.

En maskine med tilfældig adgang med et endeligt sæt instruktioner og ubegrænset lagerplads er en anden maskinemodel, der er lige så kraftig som Turing-maskinmodellen.

Af hensyn til denne diskussion skal vi ikke genere os med den nøjagtige maskinemodel, vi bruger, men snarere nok til at sige, at maskinen har en endelig deterministisk kontrolenhed, ubegrænset lagerplads 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 fortrolig med “big-O” notation så her er kun en hurtig opdatering.

Lad f : N → være en funktion.Sættet O ( f ) indeholder alle funktioner g : N → N for hvilke der findes konstanter n ₀ ∈ N og c ∈ N således at for hver n ∈ N med n > n ₀ det er sandt, at g ( n ) ≤ c f ( n ).

Nu er vi parat til at nærme os det virkelige spørgsmål.

Klassen P indeholder alle sprog L som der findes en Turing-maskine D der bestemmer L og en konstant k ∈ N sådan at for hver input w , D stopper efter højst T (| w |) trin for en funktion T ∈ O ( n ↦ n ^k ).

Siden O ( n ↦ n i Selvom det 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(n^k ).

Bemærk, at båndet afhænger af længden af w . Derfor er det argument, du fremfører for primersproget, kun korrekt for tal i unaray-kodninger , hvor for kodningen w af et tal n , længden af kodningen | w | 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 input er kodet i binær (eller til en hvilken som helst anden base). (På trods af massiv interesse kunne dette kun bevises af Manindra Agrawal, Neeraj Kayal og Nitin Saxena i et prisvindende papir i 2004, så du kan gætte på, at algoritme er ikke særlig enkel.)

De trivielle sprog {} og Σ ^＊ og det ikke-trivielle sprog { ε } findes naturligvis i P (for ethvert alfabet Σ ). Kan du skrive funktioner på dit yndlingsprogrammeringssprog, 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 beviser, at din funktion har polynomisk kørselstidskompleksitet?

Hvert almindeligt sprog (et sprog beskrevet med et regulært udtryk) er i P .

Lad Σ være et alfabet og L ⊆ Σ ^＊ . En maskine V der tager en kodet tuple med to ord w , c ∈ Σ ^＊ og output 0 eller 1 efter et endeligt antal trin er en verifier til L hvis den har følgende egenskaber.

• Givet ( w , c ), V udgange kun 1 hvis w ∈ L .
• For hver w ∈ L er der findes en c ∈ Σ ^＊ sådan at V ( w , c ) = 1.

c i ovenstående definition kaldes et vidne (eller certifikat ) .

En verifikator har tilladelse til at give falske negativer for det forkerte vidne, selvom w 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 sproget COMPOSITE, der indeholder decimalkodning af alle heltal, der er ikke primære , et vidne kunne være en faktorisering. For eksempel er (659, 709) et vidne for 467231 ∈ COMPOSITE. Du kan let kontrollere, at det på et ark papir er uden vidnet, at bevise, at 467231 ikke er prime, ville være vanskeligt uden at bruge en computer.

Vi sagde ikke noget om, hvordan et passende vidne kan være fundet. Dette er den ikke-deterministiske del.

Klassen NP indeholder alle sprog L som der findes en Turing-maskine V der verificerer L og en konstant k ∈ N sådan at for hver input ( w , c ), V stopper efter højst T (| w |) trin til en funktion T ∈ O ( n ↦ n^k ).

Bemærk, at ovenstående definition indebærer, at der for hver w ∈ L findes et vidne c med | c | ≤ T (| w |). (Turing-maskinen kan umuligt se på flere vidnesymboler.)

NP er et supersæt af P (hvorfor?). Det vides ikke, om der findes sprog, der findes i NP men ikke i P .

Heltalsfaktorisering er ikke et sprog i sig selv. Vi kan dog konstruere et sprog, der repræsenterer beslutningsproblemet , der er knyttet til det. Det vil sige et sprog, der indeholder alle tupler ( n , m ), således at n har en faktor d med d ≤ m . Lad os kalde dette sprog FAKTOR. Hvis du har en algoritme til at bestemme FACTOR, kan den bruges til at beregne en fuld faktorisering med kun polynomial overhead ved at udføre en rekursiv binær søgning efter hver primfaktor.

Det er let at vise, at FACTOR 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 ≤ m og n mod d = 0. Alt dette kan gøres på polynomisk tid. (Husk igen, at det er længden af kodningen , der tæller, og at det er logaritmisk i n .)

Hvis du kan vise, at FACTOR også er i P , kan du være sikker på at få mange seje priser. (Og du har brudt en betydelig del af nutidens kryptografi.)

For hvert sprog i NP er der en brute-force algoritme, der beslutter det deterministisk. Det udfører simpelthen en udtømmende søgning på alle vidner. (Bemærk, at et vidnes maksimale længde er afgrænset af et polynom.) Så din algoritme til at beslutte PRIMES var faktisk en brutal kraftalgoritme til at beslutte KOMPOSIT.

For at imødekomme dit sidste spørgsmål er vi nødt til at introducere 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 Σ være et alfabet og A og B være sprog over Σ . A er polynomisk tid mange-en reducerbar til B hvis der findes en funktion f : Σ ^＊ → Σ ^＊ med følgende egenskaber.

• w ∈ A   ⇔   f ( w ) ∈ B   for alle w ∈ Σ ^＊ .
• Funktionen f kan beregnes af en Turing-maskine for hver input w i et antal trin afgrænset af et polynom i | w |.

I dette tilfælde skriver vi A ≤ _p B .

For lad f.eks. A være det sprog, der indeholder alle grafer (kodet som nærhedsmatrix), der indeholder en trekant. (En trekant er en cyklus med længde 3.) Lad yderligere B være det sprog, der indeholder alle matricer med ikke-nul spor. (Sporet af en matrix er summen af dens vigtigste diagonale elementer.) Derefter er A polynomisk tid mange-en reducerbar til B . For at bevise dette er vi nødt til at finde en passende transformationsfunktion f . I dette tilfælde kan vi indstille f til at beregne 3 ^rd styrken af adjacency matrixen. Dette kræver to matrixmatrixprodukter, som hver har polynomskompleksitet.

Det er trivielt sandt, at L ≤ _p L . (Kan du bevise det formelt?)

Vi anvender dette på NP nu.

Et sprog L er NP -hard hvis og kun hvis L “≤ _p L for hvert sprog L ” ∈ NP .

Et NP -hårdt sprog kan eller ikke være i NP i sig selv.

Et sprog L er NP -komplet hvis og kun hvis

• L ∈ NP og
• L er NP -hard.

Det mest berømte NP -komplette sprog er SAT. Den indeholder alle boolske formler, der kan opfyldes. For eksempel ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Et gyldigt vidne er { a = 1, b = 0}. Formlen ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Hvordan ville du bevise det?)

Det er ikke svært at vise, at SAT ∈ NP . At vise SAT NP -hardheden 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 andre sprogs NP -komplethed via reduktion. Hvis sprog A vides at være NP -hårdt, så viser at A ≤ _p B viser, at B også er NP -hård (via transitiviteten af “≤ _p ”). I 1972 Richard Karp offentliggjorde en liste med 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 er det ikke svært at forstå og giver en meget god idé om, hvordan bevisning af NP -komplethed via reduktion fungerer. )

Endelig et kort resume. Vi bruger symbolerne NPH og NPC til at betegne klasser af NP -hard og NP -komplette sprog hhv.

• P ⊆ NP
• NPC ⊂ NP og NPC ⊂ NPH faktisk NPC = NP ∩ NPH pr. definition
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Bemærk, at inkluderingen NPC ⊂ 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 også trivielle sprog i P som ikke-trivielle sprog i NP . Thi s er dog en (ikke særlig interessant) hjørnesag.

Addendum

Din primære kilde til forvirring ser ud til at være, at du tænkte på “ n ”i“ O ( n ↦ f ( n )) ”Som fortolkning af en algoritmes input, når det 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 kodningen , der bruges til input.

Denne uge er en ny rekord for den største kendte id = “5aec42341e”> Mersenne prime blev opnået. Det største i øjeblikket kendte primtal er 2 ^{74   207   281} – 1. Dette tal er så stort at det giver mig hovedpine, så jeg bruger en mindre i følgende eksempel: 2 ³¹ – 1 = 2   147   483   647. Det kan kodes på forskellige måder.

• af sin Mersenne-eksponent som decimalnummer: 31 (2 byte)
• som decimaltal: 2147483647 (10 bytes)
• som unary nummer: 11111…11 hvor … skal erstattes af 2   147   483   640 mere 1 s (næsten 2 GiB)

Alle disse strenge koder det samme nummer og givet en af disse kan vi nemt konstruere enhver anden kodning af det samme nummer. (Du kan erstatte decimalkodning med binær, oktal eller hexadeci mal hvis du vil. Det ændrer kun længden med en konstant faktor.)

Den naive algoritme til test af primalitet er kun polynomisk for unary kodninger. AKS primality test er polynom for decimal (eller enhver anden base b ≥ 2 ). Lucas-Lehmer primality test er den bedst kendte algoritme for Mersenne primtal M _p 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 bruges. Det vil sige binært for heltal. (Bemærk, at ikke hvert primtal er en Mersenne-prime, så brug af Mersenne-eksponenten er ikke en generel kodningsplan.)

I teoretisk kryptografi sendes mange algoritmer formelt en helt ubrugelig streng på k 1 er som den første parameter. Algoritmen ser aldrig på denne parameter, men den tillader, at den formelt er polynom i k , som er sikkerhedsparameter 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 numre skiftes til unary. Beslutningssprogene for andre problemer forbliver NP -komplette selv da. Sidstnævnte kaldes stærkt NP -komplet . Det mest kendte eksempel er binpakning .

Det er også (og måske mere) interessant at se, hvordan kompleksiteten af en algoritme ændres, hvis input er komprimeret . For eksempel på Mersenne-primtal har vi set tre kodninger, som hver er logaritmisk mere komprimeret end sin forgænger.

I 1983 Hana Galperin og Avi Wigderson har skrevet et interessant papir om kompleksiteten af almindelige grafalgoritmer, når inputkodningen af grafen komprimeres logaritmisk. For disse input bliver sproget for grafer, der indeholder en trekant ovenfra (hvor det tydeligt var i P ) pludselig NP -komplet.

Og det “fordi sprogklasser som P og NP er defineret for sprog , ikke for problemer .

Kommentarer

• Dette svar er sandsynligvis ikke nyttigt for niveauet af forståelse for spørgeren. Læs de andre svar og se, hvad Nanako kæmper med. Tror du dette svar vil hjælpe ham / hende?
• Dette svar hjælper måske ikke OP, men hjælper bestemt andre læsere (mig selv inkluderet).
• meget nyttigt svar! bør overveje at rette matematiske symboler ikke korrekt vises.

Svar