Du er i utgangspunktet riktig om P og NP, men ikke om NP-hard og NP-komplett.

For det første, her er de superkornede definisjonene av de fire aktuelle kompleksitetsklassene:

• P er klassen av beslutningsproblemer som kan løses i polynomtid med en deterministisk Turing-maskin.

• NP er klassen av beslutningsproblemer som kan løses i polynomisk tid av en ikke-deterministisk Turing-maskin. Tilsvarende er det klassen av problemer som kan verifiseres i polynomisk tid av en deterministisk Turing-maskin.

• NP-hard er klassen av beslutningsproblemer som alle problemer i NP kan være redusert til i polynomisk tid av en deterministisk Turing-maskin.

• NP-komplett er skjæringspunktet mellom NP-hard og NP. Tilsvarende er NP-komplett klassen av beslutningsproblemer i NP som alle andre problemer i NP kan reduseres til på polynomisk tid av en deterministisk Turing-maskin.

Og her «sa Euler diagram fra Wikipedia som viser forholdet mellom disse fire klassene (forutsatt at P ikke er lik NP):

Den delen som jeg antar at du er mest ukjent med eller forvirret av er forestillingen om en «polynomisk tidsreduksjon» fra problem X til problem Y. En reduksjon fra X til Y er ganske enkelt en algoritme A som løser X ved å benytte seg av en annen algoritme B som løser problem Y. Denne reduksjonen kalles en » polynomisk tidsreduksjon «hvis alle deler av A annet enn B har en polynomisk tidskompleksitet. Som et trivielt eksempel er problemet med å finne det minste elementet i en matrise konstant redusert til sorteringsproblemet, siden du kan sortere matrisen og deretter returnere det første elementet i den sorterte matrisen.

En ting som er lett å gå glipp av med NP-hard definisjonen er at reduksjonen går fra NP-problemer til NP-harde problemer, men ikke nødvendigvis omvendt . Dette betyr at NP-harde problemer kan være i NP, eller i en mye høyere kompleksitetsklasse (som du kan se fra Euler-diagrammet), eller de kan ikke engang være avgjørende problemer.Derfor sier folk ofte noe sånt som «NP-hard betyr minst like hardt som NP» når de prøver å forklare disse tingene uformelt.

Stoppeproblemet er et godt eksempel på et NP-hardt problem som «er tydeligvis ikke i NP, som Wikipedia forklarer :

Det er lett å bevise at det stoppende problemet er NP-vanskelig, men ikke NP-komplett. For eksempel kan det boolske tilfredsstillelsesproblemet reduseres til det stoppende problemet ved å transformere det til beskrivelsen av en Turing-maskin som prøver alle sannhetsverditildelinger, og når den finner en som tilfredsstiller formelen, stopper den og ellers går den i en uendelig løkke. Det er også lett å se at stoppeproblemet ikke er i NP, siden alle problemer i NP kan avgjøres i et endelig antall operasjoner, mens stoppeproblemet generelt er ubeslutbart.

Kommentarer

• @Nakano Intuitivt, det ‘ sa » reduksjon » i den forstand at ett problem blir gjort til et underproblem av et annet problem. Det faktum at noen av disse reduksjonene øker kompleksiteten i stedet for å redusere den gjennom dårlig valg av » underproblem » betyr ganske enkelt at du aldri vil bruke disse reduksjonene i hvilken som helst ekte verdenskode. Selv om jeg for å være ærlig NP-hard, virker det som en rar og ikke veldig interessant klasse; det kan være mer fruktbart å ignorere det og bare tenke på NP-komplett som settet med NP-problemer som alle andre NP-problemer reduserer til.
• @Nakano stackoverflow.com/questions/12637582/… Jeg tror det korte svaret er at når folk snakker om at heltalsfaktorisering er NP, ‘ snakker normalt om veldig store heltall, som du vanligvis begynner å gjøre dine store O-bevis med n som » antall bits heltallet tar opp i minnet » i stedet for » antall heltall du sendte til funksjonen «.
• @Nakano: I stor-O-notasjon er n et mål for størrelsen på inngangen (antall elementer, byte, sifre osv.), Ikke verdien av input.
• @Nakano Det korte svaret er at du ‘ har det bra, og det er derfor når du gjør tid co mplexity analaysis du må alltid spesifisere hva n betyr . Påstanden om at n er » størrelsen på inngangen » er bare et kort sammendrag av hvordan vi normalt velger å definere n. Det ‘ er ikke en del av de strenge definisjonene av big-O-notasjon eller tidskompleksitet. Jeg tror du har rett i å si at heltallfaktorisering er O (sqrt (n)) når n er -verdien av inngangen. Det skjer slik at kompleksitetsresultatene der n betyr størrelse vanligvis er mye mer nyttige i praksis enn de der n betyr verdi.
• @Nakano Det ‘ Det er også verdt å huske at teknisk at du også må definere tidskompleksiteten til dine primitive operasjoner (tillegg, multitplikasjon, lesing fra minne, skriving til minne, sammenligning av to tall). Det meste av tiden antar vi at alle disse primitivene er konstante, eller vi teller bare en slags operasjon (f.eks. For sorteringsalgoritmer teller vi tradisjonelt sammenligningene). Jeg mistenker at resultatene for heltallfaktorisering ikke ‘ antar at alle disse operasjonene er konstant tid som vi vanligvis gjør, ellers ville størrelsen på tallet ikke ‘ t betyr veldig mye.

Heltalsfaktorisering blir sitert som et eksempel på NP, men jeg forstår ikke hvorfor det ikke er P, personlig, siden prøvefaktorisering tar O (sqrt (n)) tid.

For kompleksitetsklasser er n lengden på inngangen. Så hvis du vil faktorere heltall k, er n ikke k men log k, antall biter (eller hva som helst) det tar å skrive ned tallet. Så heltal faktorisering er O(sqrt(k)) som du sier, men dette er O(sqrt(2n)) som er O(2(n/2)).

NP-Hard antar jeg at den bare er full av ukjente. Vanskelig å verifisere, vanskelig å løse.

Nei. NP-Hard handler bare om hvor vanskelig et problem er å løse.

NP-Hard-problemer er i det minste harde som det vanskeligste problemet i NP. Vi vet at de er i det minste så harde, for hvis vi hadde en polynomialtidsalgoritme for et NP-Hard-problem, kunne vi tilpasse den algoritmen til ethvert problem i NP.

NP-Complete Jeg forstår ikke i det hele tatt

NP- Komplett betyr at et problem er både NP og NP-hardt. Det betyr at vi kan verifisere en løsning raskt (NP), men det er minst like vanskelig som det vanskeligste problemet i NP (NP-Hard).

Jeg vet ikke helt hva det betyr for det å være ikke-deterministisk.

Ikke -bestemmelse er en alternativ definisjon av NP. En ikke-deterministisk turingmaskin er i stand til å duplisere seg selv når som helst, og få hvert duplikat til å utføre en annen utførelsesbane. Under denne definisjonen er NP settet med problemene som kan løses i polynomisk tid av en datamaskin enn det fritt kan duplisere seg selv. Det viser seg at dette er nøyaktig det samme settet med problemer som kan verifiseres på polynomisk tid.

Kommentarer

• Så det er mulig for $ O ( n ^ k) $ time algoritmer for å være NP problemer?
• k er et konstant reelt tall? Ja. Alle P-problemer er også NP-problemer. Tydeligvis kan alt du kan løse i polynomisk tid også verifiseres i polynomisk tid.
• Hvordan defineres lengde / størrelse egentlig her? For eksempel kunne jeg bare skrive $ n $ i en stor base og redusere lengden når den er skrevet. Hva med problemer som ikke ‘ t eksplisitt håndterer heltall, men sier grafer med $ V $ toppunkt og $ E $ kanter osv.
• @Nakano, faktisk en stor base ville ‘ ikke endre den, fordi den bare ville være en konstant faktorforskjell. Så det ville ‘ ikke påvirke polynom mot ikke-polynom. Imidlertid, hvis du skrev tallet på unary, ville det endre det.
• @Nakano, hmm … Jeg ville ikke ‘ t å prøve å forklare kompleksiteten klasser til en femåring. : P

Det første du må forstå er at P og NP klassifisere 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.

{0 , 1} er et alfabet som ASCII-tegnsettet er. {} 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 sammenføyning av et endelig antall symboler fra Σ kalles et ord over Σ .

Strengen 101 er et ord over alfabetet {0, 1}. Det tomme ordet (ofte skrevet som ε ) er et ord over ethvert alfabet. Strengen penguin er et ord over alfabetet som inneholder ASCII-tegnene. Desimalnotasjonen av tallet π er ikke et ord over alfabetet {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} fordi den ikke er endelig.

lengde av 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. Settet Σ ^＊ inneholder alle ord over Σ , inkludert ε . Settet Σ ⁺ inneholder alle ord over Σ , unntatt ε . For n ∈ N , Σ ⁿ er settet med ord med lengde n .

For hvert alfabet Σ , Σ ^＊ og Σ ⁺ er uendelige tellbare sett .For ASCII-tegnsettet Σ _ASCII , blir de regulære uttrykkene .* og .+ betegne Σ _ASCII ^＊ og Σ _ASCII ⁺ .

{0, 1} ⁷ er settet med 7-biters ASCII-koder {0000000, 0000001,…, 1111111}. {0, 1} ³² er settet med 32-biters heltallverdier.

La Σ være et alfabet og L ⊆ Σ ^＊ . L kalles et språk over Σ .

For et alfabet Σ , tomt sett og Σ ^＊ er trivielle språk over Σ . 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.

Delsett av {0, 1} ³² som tilsvarer ikke-NaN IEEE 754 flytende punktverdier er et endelig språk.

Språk kan ha et uendelig antall ord, men hvert språk kan telles. Sett med strenger {1, 2,…} som betegner heltallene i desimaltegning er et uendelig språk over alfabetet {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. Det uendelige settet med strenger {2, 3, 5, 7, 11, 13,…} som angir primtallene i desimalnotasjon, er en riktig delmengde derav. Språket som inneholder alle ord som samsvarer med det regulære uttrykket [+-]?\d+\.\d*([eE][+-]?\d+)?, er et språk over ASCII-tegnsettet (som angir en delmengde av de gyldige flytende punktuttrykkene 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 ⊆ Σ ^＊ . En maskin D bestemmer L hvis for hver inngang w ∈ Σ ^＊ den beregner karakteristisk funksjon χ _L ( w ) på endelig tid. Den karakteristiske funksjonen er definert som

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

En slik maskin kalles en avgjøreren for L . Vi skriver « D ( w ) = x » for «gitt w , D utganger x ”.

Det er mange maskinemodeller. Den mest generelle som er i praktisk bruk i dag er modellen til en Turing-maskin . En Turing-maskin har ubegrenset lineær lagring samlet i celler. Hver celle kan inneholde nøyaktig ett symbol på et alfabet når som helst. Turing-maskinen utfører sin beregning som en sekvens av beregningstrinn. I hvert trinn kan den lese en celle, eventuelt overskrive verdien og flytte lese / skrivehodet med en posisjon til venstre eller høyre celle. Hvilken handling maskinen vil utføre styres av en endelig tilstandsautomat.

En tilfeldig tilgangsmaskin med et endelig sett med instruksjoner og ubegrenset lagring er en annen maskinemodell som er like kraftig som Turing-maskinmodellen.

Av hensyn til denne diskusjonen skal vi ikke bry oss om den nøyaktige maskinemodellen vi bruker, men heller være 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 oppdatering.

La f : N → være en funksjon.Settet O ( f ) inneholder alle funksjonene g : N → N som det eksisterer konstanter for n ₀ ∈ N og c ∈ N slik at for hver n ∈ N med n > n ₀ det stemmer at g ( n ) ≤ c f ( n ).

Nå er vi forberedt på å nærme oss det virkelige spørsmålet.

Klassen P inneholder alle språk L som det finnes en Turing-maskin D som bestemmer L og en konstant k ∈ N slik at for hver inngang w , D stopper etter høyst T (| w |) trinn for en funksjon T ∈ O ( n ↦ n ^k ).

Siden O ( n ↦ n i Selv om det er matematisk riktig, er det upraktisk å skrive og lese, de fleste – for å være ærlige, alle bortsett fra meg selv – skriver vanligvis ganske enkelt O(n^k ).

Merk at båndet avhenger av lengden på w . Derfor er argumentet du fremfører for primærspråket bare riktig for tall i unaray-kodinger , hvor for kodingen w av et tall n , lengden på kodingen | w | er proporsjonal med n . Ingen vil 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 til primtall forblir i P hvis inngangene er kodet i binær (eller til en hvilken som helst annen base). (Til tross for massiv interesse, kunne 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 er ikke veldig enkel.)

De trivielle språkene {} og Σ ^＊ og det ikke-trivielle språket { ε } er åpenbart i P (for ethvert alfabet Σ ). Kan du skrive funksjoner i favorittprogrammeringsspråket ditt som tar en streng som input og returnerer en boolsk fortelling om strengen er et ord fra språket for hver av disse, og bevise at funksjonen din har polynomisk kjøretidskompleksitet? p> Hvert vanlige språk (et språk beskrevet av et vanlig uttrykk) er i P .

La Σ være et alfabet og L ⊆ Σ ^＊ . En maskin V som tar en kodet tuple med to ord w , c ∈ Σ ^＊ og sender ut 0 eller 1 etter et endelig antall trinn er en verifier for L hvis den har følgende egenskaper.

• Gitt ( w , c ), V utganger 1 bare hvis w ∈ L .
• For hver w ∈ L , der eksisterer en c ∈ Σ ^＊ slik at V ( w , c ) = 1.

c i definisjonen ovenfor kalles et vitne (eller sertifikat ) .

En verifier har lov til å gi falske negativer for feil vitne, selv om w faktisk er i L . Det er imidlertid ikke lov å gi falske positive. Det kreves også at det for hvert ord i språket eksisterer minst ett vitne.

For språket COMPOSITE, som inneholder desimalkodingene til alle heltall som er ikke prime , et vitne kan være en faktorisering. For eksempel er (659, 709) et vitne for 467231 ∈ COMPOSITE. Du kan enkelt bekrefte at det på et papirark uten vitnet er gitt, å bevise at 467231 ikke er førsteklasses ville være vanskelig uten å bruke en datamaskin.

Vi sa ikke noe om hvordan et passende vitne kan være funnet. Dette er den ikke-deterministiske delen.

Klassen NP inneholder alle språk L som det finnes en Turing-maskin V som verifiserer L og en konstant k ∈ N slik at for hver inngang ( w , c ), V stopper etter maksimalt T (| w |) trinn for en funksjon T ∈ O ( n ↦ n^k ).

Merk at definisjonen ovenfor innebærer at for hver w ∈ L eksisterer et vitne c med | c | ≤ T (| w |). (Turing-maskinen kan umulig se på flere symboler for 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 .

Heltalsfaktorisering 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 tuplene ( n , m ) slik at n har en faktor d med d ≤ m . La oss kalle dette språket FAKTOR. Hvis du har en algoritme som bestemmer FACTOR, kan den brukes til å beregne en full faktorisering med bare polynomial overhead ved å utføre et rekursivt binært søk etter hver primfaktor.

Det er lett å vise at FACTOR er i NP . Et passende vitne vil ganske enkelt være faktoren d i seg selv, og alt verifisereren må gjøre er å verifisere at d ≤ m og n mod d = 0. Alt dette kan gjøres på polynomisk tid. (Husk igjen at det er lengden på kodingen som teller, og at det er logaritmisk i n .)

Hvis du kan vise at FACTOR 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 ganske enkelt et uttømmende søk over alle vitner. (Merk at den maksimale lengden på et vitne er avgrenset av et polynom.) Så algoritmen din for å bestemme PRIMES var faktisk en brute-force algoritme for å bestemme COMPOSITE. p>

For å løse det endelige spørsmålet ditt, må vi introdusere reduksjon . Reduksjoner er et veldig kraftig begrep med teoretisk informatikk. Å redusere ett problem til et annet betyr i utgangspunktet å løse et problem ved å løse et annet problem.

La Σ være et alfabet og A og B være språk over Σ . A er polynomtid mange-en reduserbar til B hvis det finnes en funksjon f : Σ ^＊ → Σ ^＊ med følgende egenskaper.

• w ∈ A   ⇔   f ( w ) ∈ B   for alle w ∈ Σ ^＊ .
• Funksjonen f kan beregnes av en Turing-maskin for hver inngang w i et antall trinn avgrenset av et polynom i | w |.

I dette tilfellet skriver vi A ≤ _p B .

For eksempel, la A være språket som inneholder alle grafer (kodet som nærhetsmatrise) som inneholder en trekant. (En trekant er en syklus med lengde 3.) La videre B være språket som inneholder alle matriser med ikke-spor. (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 stille f til å beregne 3 ^rd -styrken til nærhetsmatrisen. Dette krever to matrisematriksprodukter, som hver har polynomskompleksitet.

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

Vi bruker dette på NP nå.

Et språk L er NP -hard hvis og bare hvis L «≤ _p L for hvert språk L » ∈ NP .

Et NP -hardt språk kan være eller ikke i selve NP .

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 oppfylles. For eksempel ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Et gyldig vitne er { a = 1, b = 0}. Formelen ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Hvordan vil 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 -kompletten til andre språk via reduksjon. Hvis språk A er kjent for å være NP -hard, viser det at A ≤ _p B viser at B også er NP -hard (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 det å bevise NP -komplethet via reduksjon fungerer. )

Endelig et kort sammendrag. Vi bruker symbolene NPH og NPC for å betegne klassene NP -hard og NP -komplett språk. henholdsvis.

• P ⊆ NP
• NPC ⊂ NP og NPC ⊂ NPH , faktisk NPC = NP ∩ NPH per definisjon
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Merk at inkluderingen NPC ⊂ NP er riktig selv i tilfelle P = NP . For å se dette, gjør deg klar over at intet ikke-trivielt språk kan reduseres til et trivielt språk, og det er trivielle språk i P også som ikke-trivielle språk i NP . Thi s er imidlertid et (ikke veldig interessant) hjørnesak.

Tillegg

Din primære kilde til forvirring ser ut til å være at du tenkte på « n ”i“ O ( n ↦ f ( n )) ”Som tolkning av en algoritmes inngang når den faktisk refererer til lengden av inngangen. Dette er et viktig skille fordi det betyr at den asymptotiske kompleksiteten til en algoritme avhenger av kodingen som brukes til inngangen.

Denne uken ble en ny rekord for den største kjente Mersenne prime ble oppnådd. Det største nåværende kjente primtallet er 2 ^{74   207   281} – 1. Dette tallet er så stort at det gir meg hodepine, så jeg bruker en mindre i følgende eksempel: 2 ³¹ – 1 = 2   147   483   647. Den kan kodes på forskjellige måter.

• av sin Mersenne-eksponent som desimaltall: 31 (2 byte)
• som desimaltall: 2147483647 (10 byte)
• som unary nummer: 11111…11 der … skal erstattes av 2   147   483   640 flere 1 s (nesten 2 GiB)

Alle disse strengene koder det samme nummeret og gitt noen av disse, kan vi enkelt lage en hvilken som helst annen koding med samme nummer. (Du kan erstatte desimalkoding med binær, oktal eller heksadeci mal hvis du vil. Det endrer bare lengden med en konstant faktor.)

Den naive algoritmen for å teste primality er bare polynom for unary koding. AKS primality test er polynom for desimal (eller en hvilken som helst annen base b ≥ 2 ). Lucas-Lehmer primality test er den mest kjente algoritmen for Mersenne primtall M _p med p en merkelig prim, men den er fortsatt eksponentiell i lengden på den binære kodingen til Mersenne-eksponenten p (polynom i p ).

Hvis vi vil snakke om kompleksiteten til en algoritme, er det veldig viktig at vi er veldig tydelige hvilken representasjon vi bruker. Generelt kan man anta at den mest effektive kodingen brukes. Det vil si binært for heltall. (Merk at ikke hvert primtall er en Mersenne-primtall, så bruk av Mersenne-eksponenten er ikke et generelt kodingsskjema.)

I teoretisk kryptografi blir mange algoritmer formelt gitt en helt ubrukelig streng på k 1 er som første parameter. Algoritmen ser aldri på denne parameteren, men den lar den formelt være polynom i k , som er sikkerhetsparameter brukes til å stille sikkerheten til prosedyren.

For noen problemer som beslutningsspråket i binær koding er NP -komplett, er ikke beslutningsspråket lenger NP -komplett hvis kodingen av innebygde tall er 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 er komprimert . For eksempel på Mersenne-primtall, har vi sett tre kodinger, som hver er logaritmisk mer komprimert enn forgjengeren.

I 1983 Hana Galperin og Avi Wigderson har skrevet en interessant artikkel om kompleksiteten til vanlige grafalgoritmer når inngangskodingen av grafen komprimeres logaritmisk. For disse inngangene blir språket til grafer som inneholder en trekant ovenfra (der det var tydelig i P ) plutselig NP -komplett.

Og det «fordi språkklasser som P og NP er definert for språk , ikke for problemer .

Kommentarer

• Dette svaret er sannsynligvis ikke nyttig for forståelsesnivået til spøreren. Les de andre svarene og se hva Nanako sliter med. Tror du dette svaret vil hjelpe ham / henne?
• Dette svaret hjelper kanskje ikke OP, men hjelper absolutt andre lesere (meg selv inkludert).
• veldig nyttig svar! bør vurdere å fikse matematikksymbolene ikke riktig vises.

Jeg vil prøve å gi deg mindre uformell definisjon for det samme.

P-problemer: problemer som kan løses i polynomisk tid. Inneholder problemer som kan løses effektivt.

NP-problem: problemer som kan verifiseres i polyno mial tid. For eksempel: Reisende selger, kretsdesign. NP-problemer er som puslespill (som sudoku). Gitt en riktig løsning for problemet, kan vi sjekke løsningen vår veldig raskt, men hvis vi faktisk prøver å løse det, kan det bare ta evig tid.

Nå spør P vs NP om et problem hvis løsning kan være raskt sjekket for å være riktig, så er det alltid en rask måte å løse det på. Dermed skriver du matematisk: er NP en delmengde av P eller ikke?

Nå kommer vi tilbake til NP fullført: dette er de virkelig harde problemene med NP-problemene. Derfor, hvis det er en raskere måte å løse NP fullstendig på, blir NP komplett P og NP problemer kollapser inn i P.

NP vanskelig: problemer som ikke kan kontrolleres til og med i polynomtiden er np vanskelig. For eksempel er å velge det beste trekket i sjakk en av dem.

Hvis noe forblir uklart, kan du prøve å se denne videoen: https://www.youtube.com/watch?v=YX40hbAHx3s

Jeg håper dette vil gi en uskarp kontur.