7.1 P, NP og co-NP — sertifikat og verifikasjon
Klassene P, NP og co-NP, verifikasjonsalgoritme og sertifikat, og skillet avgjørelses- vs. optimeringsproblem.
Tre oppgavesjangre henter fra dette kapitlet, og her er de i klarspråk:
- Sjanger D — definisjon «med egne ord»: du blir bedt om å forklare et begrep, og svaret er én presis setning med hovedpoenget først. «Hva er et sertifikat?» er en typisk D-oppgave.
- Sjanger F — «stemmer dette?»: du får et utsagn og svarer ja eller nei først, deretter én setning som begrunner. «Alle problemer i NP krever eksponentiell tid å løse — stemmer dette?»
- Sjanger G — reduksjon og NP-argument: du oppgir hvilken vei en reduksjon går og hva den beviser. Selve reduksjonsmaskineriet kommer i kap. 7.2, men grunnbegrepene som G-oppgavene hviler på — hva NP er — bygges her.
Eksamen er hjelpemiddelfri. NTNU bruker koden E for det, og den betyr rett og slett at ingen hjelpemidler er tillatt: definisjonene i dette kapitlet må sitte i hodet, ikke i et ark.
Den gode nyheten er at dette er puggbart og billig. Definisjonene er korte, de endrer seg ikke fra år til år, og løsningsforslagene premierer den presise setningen framfor den lange. Én time her er noe av det best betalte du gjør i hele faget.
Forkunnskaper
Dette kapitlet bygger på fire ting du har møtt tidligere i boka:
- Asymptotisk notasjon fra kap. 1.1 og kap. 1.2. Du må kunne lese og og vite at betyr .
- Grafer og grafnotasjonen fra kap. 4.1 — noder, kanter, nabolister og nabomatrise.
- Maks-flyt fra kap. 5.1 og kap. 5.2. Vi bruker Edmonds-Karp som eksempel på et problem vi kan løse raskt.
- Mengdelære — union, snitt og delmengde. Trenger du en oppfriskning, ligger den i Mengdelære.
Du trenger ingen forkunnskaper om reduksjoner, NP-komplette problemer eller SAT. Alt det kommer i kap. 7.2 og kap. 7.3, og bygger på nettopp det du leser her.
Å lage en løsning mot å kontrollere en (~10 min)
På en sengepost settes vaktlista for neste måned. Reglene er mange: ingen jobber to nattevakter på rad, hver vakt trenger minst én sykepleier med spesialkompetanse, og ingen skal over 160 timer. Å lage en slik liste fra bunnen kan ta en avdelingsleder flere dager. Å kontrollere en ferdig liste tar en halvtime: du går gjennom vaktene én etter én og krysser av mot reglene.
Denne forskjellen — vanskelig å lage, lett å kontrollere — er hele grunnlaget for kapitlet. Kompleksitetsteorien tar den intuisjonen og gjør den presis. Klassen handler om hva vi klarer å lage. Klassen handler om hva vi klarer å kontrollere.
Før vi kan definere klassene, må vi rydde i én ting: hva slags spørsmål de handler om.
Et problem der svaret alltid er ja eller nei — ingenting annet. «Finnes det en vaktliste som oppfyller alle reglene?» er et avgjørelsesproblem; «hvilken vaktliste er best?» er det ikke.
Hele kompleksitetsteorien er bygd på avgjørelsesproblemer, fordi et ja/nei-svar er lett å sammenligne på tvers av problemer. Når du ser og definert, er det alltid mengder av avgjørelsesproblemer.
En instans av problemet er én konkret input — den konkrete grafen, den konkrete tallmengden. Instansen kalles en ja-instans hvis svaret er ja, og en nei-instans hvis svaret er nei.
Et problem der du søker den beste løsningen etter et mål: den korteste ruta, det letteste spenntreet, den største flyten. Svaret er en løsning eller en verdi, ikke ja/nei.
De fleste problemene du har møtt i boka så langt er optimeringsproblemer: korteste vei, minimalt spenntre, maksimal flyt. Kompleksitetsteorien håndterer dem indirekte, gjennom avgjørelsesvarianten under.
Du gjør et optimeringsproblem om til et avgjørelsesproblem ved å legge til en terskelverdi i inputen og spørre om målet kan nås:
- optimering: «hva er den korteste rundturen?»
- avgjørelse: «finnes det en rundtur med lengde høyst ?»
Koblingen går begge veier og er poenget med grepet: er avgjørelsesvarianten vanskelig, er optimeringsvarianten minst like vanskelig. Kunne du regne ut den korteste rundturen raskt, ville du også kunne svare på terskelspørsmålet raskt — bare sammenlign svaret med . Derfor holder det å studere avgjørelsesvarianten.
En budbil skal innom tre utleveringspunkter og tilbake til hovedlageret. Avstandene i kilometer er:
| Hovedlageret | Nordbakken | Sjøkanten | Vestmarka | |
|---|---|---|---|---|
| Hovedlageret | — | 90 | 130 | 70 |
| Nordbakken | 90 | — | 60 | 150 |
| Sjøkanten | 130 | 60 | — | 110 |
| Vestmarka | 70 | 150 | 110 | — |
a) Skriv optimeringsproblemet «finn den korteste rundturen» om til et avgjørelsesproblem.
b) Er instansen med terskel en ja-instans? Er den med det?
b) De tre distinkte rundturene har lengdene 330 km, 410 km og 480 km (de seks rekkefølgene faller sammen to og to, siden en rundtur og dens speilvending er like lange). Korteste rundtur er altså 330 km, via Hovedlageret – Nordbakken – Sjøkanten – Vestmarka – Hovedlageret.
- : ja-instans, fordi .
- : nei-instans, fordi ingen rundtur er kortere enn 330 km.
Legg merke til hva svaret ikke er: oppgaven spør om ja eller nei, ikke om hvilken rute som er kortest. Ja/nei er hele svaret på et avgjørelsesproblem.
Fem målestasjoner skal knyttes sammen med kabel. Kabelstrekkene som er mulige, har lengdene: 1–2: 4 km, 1–3: 7 km, 2–3: 3 km, 2–4: 9 km, 3–4: 5 km, 3–5: 8 km, 4–5: 6 km.
a) Skriv om optimeringsproblemet «finn det billigste nettet som knytter alle fem stasjonene sammen» til et avgjørelsesproblem.
b) Det minimale spenntreet har samlet lengde 18 km. Er instansen med terskel en ja-instans? Hva med ?
Klassen P — det vi klarer å regne ut (~8 min)
Nesten alle algoritmene i denne boka er raske i en helt bestemt forstand: kjøretiden er begrenset av inputstørrelsen opphøyd i en fast potens. Merge-Sort bruker , MST-Kruskal bruker , Edmonds-Karp bruker . Alle tre vokser som et polynom i inputstørrelsen. Det er nettopp den egenskapen klassen fanger.
En algoritme kjører i polynomisk tid hvis kjøretiden er for en konstant som ikke avhenger av inputen. Her er størrelsen på inputen, altså hvor mange symboler den fyller — ikke hvor store tallene i den er.
, , og er polynomiske. og er det ikke: der vokser kjøretiden raskere enn et hvilket som helst polynom. Forskjellen er ikke akademisk. For er , mens er over — en faktor på mer enn ni milliarder.
Faggrensen mellom «håndterbart» og «ikke håndterbart» settes ved polynomisk tid. Det er en tommelfingerregel, ikke en naturlov: en algoritme på er polynomisk og likevel ubrukelig. Men i praksis har de polynomiske algoritmene vi faktisk finner, små eksponenter, og skillet har vist seg å være det nyttigste vi har.
Mengden av alle avgjørelsesproblemer som kan løses av en algoritme i polynomisk tid. «Løses» betyr her at algoritmen selv finner ja/nei-svaret — den får ingen hjelp.
Alle grafalgoritmene i Del 4 og flytalgoritmene i Del 5 vitner om problemer i : «finnes det en vei fra s til t med lengde høyst ?» ligger i fordi Dijkstra løser optimeringsvarianten i . Tilsvarende for spenntre og maksimal flyt.
er den klassen som svarer til det vi vil kalle en effektiv algoritme.
Begrunn kort at hvert av disse avgjørelsesproblemene ligger i :
a) Finnes det et spenntre med samlet vekt høyst ?
b) Finnes det en flyt fra s til t med verdi minst ?
c) Er arrayet A[1..n] sortert stigende?
MST-Kruskal i , som gir det minimale spenntreets vekt, og sammenlign med . Er minimum høyst , er svaret ja; ellers nei. Sammenligningen er ett steg, så totalen er fortsatt — polynomisk.b) Ja. Kjør Edmonds-Karp i , som gir maksimal flytverdi, og sammenlign med . Edmonds-Karp velger alltid korteste forøkende sti, og det er nettopp derfor kjøretiden er polynomisk og ikke avhenger av kapasitetenes tallverdi.
c) Ja. Én gjennomgang som sammenligner A[i] med A[i+1] for avgjør det i .
Fellesnevneren er formen på svaret: oppgi algoritmen, oppgi kjøretiden, og si at den er polynomisk. Det er hele begrunnelsen en slik oppgave ber om.
Sertifikat, verifikasjon og klassen NP (~15 min)
Tilbake til vaktlista. Den som skal kontrollere den, får to ting: reglene og bemanningsbehovet (selve problemet) og den ferdige lista (den foreslåtte løsningen). Kontrolløren trenger ikke gjenskape arbeidet — hun trenger bare å krysse av.
Kompleksitetsteorien gir de to tingene navn. Den første er instansen . Den andre er sertifikatet . Og den som krysser av, er en verifikasjonsalgoritme.
Et sertifikat er den foreslåtte løsningen som følger med instansen når svaret skal kontrolleres — beviset for at svaret er ja.
For «finnes det en rundtur som besøker hver by én gang?» er sertifikatet selve rekkefølgen av byer. For «finnes det en delmengde med sum 45?» er sertifikatet delmengden. For vaktlista er sertifikatet den ferdige lista.
Sertifikatet må ha polynomisk lengde i inputstørrelsen. Uten det kravet ville definisjonen av vært tom for innhold: du kunne levert en tabell over alle mulige svar som «sertifikat», og kontrollen ville vært et oppslag. Det er kravet om kort sertifikat som gjør at kontrollen faktisk er billigere enn søket.
Merk at et sertifikat bare finnes for ja-instanser. Er svaret nei, er det ingenting å legge fram.
En algoritme som tar to argumenter — instansen og et sertifikat — og svarer 1 hvis beviser at er en ja-instans, ellers 0.
Algoritmen verifiserer problemet hvis det gjelder: er en ja-instans nøyaktig når det finnes minst ett sertifikat slik at .
En verifikasjonsalgoritme løser ikke problemet. Den avgjør bare om et foreslått svar holder. Det er hele forskjellen mellom å planlegge vaktlista og å kontrollere den.
Mengden av alle avgjørelsesproblemer der et ja-svar kan verifiseres i polynomisk tid, gitt et sertifikat av polynomisk lengde.
Les den setningen én gang til, og legg merke til hva som ikke står der. Det står ingenting om hvor lang tid det tar å finne løsningen. handler om kontroll, ikke om søk. Et problem kan ligge i og samtidig ha en lynrask løsningsalgoritme — sortering er et banalt eksempel.
Navnet forvirrer med vilje dårlig: N-en står ikke for «not». Den står for nondeterministisk, fra en eldre, likeverdig definisjon der en tenkt maskin gjetter sertifikatet og kontrollerer det. Utfallet er det samme; verifikasjonsformen er den du skal kunne skrive ned.
« er bevist.» Nei. Det er et åpent problem. Vi vet at ; om inklusjonen er streng, vet ingen. Skriv aldri noe som forutsetter at spørsmålet er avgjort.
Å blande avgjørelses- og optimeringsvarianten. «Hva er den korteste rundturen?» er ikke et avgjørelsesproblem, og hører derfor strengt tatt ikke hjemme i eller i det hele tatt. Legg til terskelen først.
Å glemme kravet om polynomisk sertifikatlengde. Uten det kan hva som helst «verifiseres», og definisjonen kollapser.
Hvorfor: la et problem ligge i , med en algoritme som avgjør det i polynomisk tid. Lag en verifikasjonsalgoritme som rett og slett kaster sertifikatet og kjører løsningsalgoritmen på . Den svarer 1 nøyaktig for ja-instansene, og den bruker samme polynomiske tid som løsningsalgoritmen. Kravet om sertifikat er oppfylt av det tomme sertifikatet, som åpenbart har polynomisk lengde.
Altså: alt som kan løses raskt, kan verifiseres raskt. Motsatt vei er det store åpne spørsmålet — om alt som kan verifiseres raskt, også kan løses raskt. Det er nøyaktig spørsmålet «er ?», og det er ubesvart.
En hamiltonsykel i en graf er en sykel som besøker hver node nøyaktig én gang og ender der den startet. Avgjørelsesproblemet «har en hamiltonsykel?» kalles HAM-CYCLE og får sin formelle definisjon i kap. 7.3. Her bruker vi det bare til å vise hvordan en verifikasjonsalgoritme ser ut.
1. Antagelser om representasjon. Grafen er urettet og gitt som nabomatrise, slik at «finnes kanten ?» er ett oppslag i konstant tid. Sertifikatet y[1..V] er en sekvens av noder, indeksert fra 1.
2. Pre-/postbetingelse. Før: y er en vilkårlig nodesekvens — den kan være hva som helst, også søppel. Etter: returverdien er 1 nøyaktig når y er en hamiltonsykel i G, ellers 0. Grafen endres ikke.
3. Pseudokoden.
Verify-Ham-Cycle(G, y)
Input: graf G = (V, E) som nabomatrise; sekvens y[1..V] av noder
Output: 1 hvis y er en hamiltonsykel i G, ellers 0
if y.length != |V|
return 0
la sett[1..|V|] vaere en boolsk tabell med alle verdier FALSE
for i = 1 to |V|
if sett[y[i]] == TRUE
return 0 // node besoekt to ganger
sett[y[i]] = TRUE
for i = 1 to |V| - 1
if (y[i], y[i+1]) not in E
return 0 // manglende kant i stien
if (y[|V|], y[1]) not in E
return 0 // sykelen lukkes ikke
return 14. Grunnideen i én setning. En nodesekvens er en hamiltonsykel nøyaktig når den inneholder hver node én gang og hvert nabopar i sekvensen — inkludert paret som lukker sykelen — er en kant.
5. Kjøretid. Den første løkka gjør oppslag i en boolsk tabell, den andre gjør oppslag i nabomatrisen, alle i konstant tid, så kontrollen er — polynomisk i inputstørrelsen. Til sammenligning ville et uttømmende søk måtte prøve sekvenser.
En inspektør skal kjøre en runde som innom hver stasjon nøyaktig én gang og ender der hun startet.
a) Oppgi et sertifikat for at en slik runde finnes, og vis at Verify-Ham-Cycle godtar det.
b) En kollega foreslår runden 1–2–3–4–5–6–1. Hva svarer verifikatoren, og hvorfor?
c) Hva ville et uttømmende søk kostet på samme instans?
Verifikatoren kontrollerer først at alle seks stasjonene forekommer nøyaktig én gang — det gjør de. Deretter slår den opp de seks nabo-parene: , , , , og til slutt som lukker sykelen. Alle seks står i kantlista, så den returnerer 1. Til sammen 6 distinkthetssjekker og 6 kantoppslag: 12 konstanttidsoperasjoner.
b) Verifikatoren returnerer 0. Kontrollen av nabo-parene stopper på , som ikke er en forbindelse i nettet. At de fem andre parene er kanter, hjelper ikke — ett brudd er nok.
c) Et uttømmende søk ville måttet prøve alle rekkefølger av de fem øvrige stasjonene etter stasjon 1, altså sekvenser. Med 20 stasjoner ville tallet vært , som er over . Det er nettopp dette gapet klassen setter ord på: kontrollen er lineær, søket er eksponentielt.
b) Hva vil det si at et problem ligger i ?
Tallene 7, 11, 15, 23 og 31 er gitt, sammen med målet 45. Spørsmålet er om noen delmengde av tallene summerer nøyaktig til målet.
a) Oppgi et sertifikat for at 45 er en ja-instans.
b) Beskriv verifikasjonsalgoritmen og oppgi kjøretiden dens.
c) Er 44 en ja-instans? Begrunn.
b) «Sortering av tall ligger i .»
c) «Hvis et problem ligger i , ligger det også i .»
co-NP og det åpne spørsmålet (~10 min)
Sertifikatet i forrige avsnitt beviste alltid et ja. Inspektøren la fram en runde, og verifikatoren sa «denne holder». Men hva med nei-svaret? Hvordan beviser du kort at det ikke finnes noen slik runde?
Det er ikke opplagt at det går an. Å legge fram alle rundene som ikke virker, er ikke et kort bevis. Denne asymmetrien har fått sitt eget navn.
Komplementet til et avgjørelsesproblem er det samme spørsmålet med ja og nei byttet om. Komplementet til «har grafen en hamiltonsykel?» er «har grafen ingen hamiltonsykel?».
Instansene er de samme; det er svarene som snus. En ja-instans i det opprinnelige problemet er en nei-instans i komplementet, og omvendt.
Mengden av avgjørelsesproblemer der komplementet ligger i — altså der nei-svaret kan verifiseres i polynomisk tid med et sertifikat.
Et eksempel: «er dette logiske uttrykket sant for alle mulige tilordninger av sannhetsverdier?» ligger i . Er svaret nei, kan du bevise det kort ved å legge fram én tilordning som gjør uttrykket usant — den tilordningen er sertifikatet for nei-svaret.
og er ikke det samme som « og alt utenfor ». De er to klasser som overlapper: alt i ligger i begge. Om , er et åpent spørsmål, akkurat som .
Alt i ligger i begge, og begrunnelsen er den samme som for : kan du regne ut svaret raskt, trenger du ikke noe sertifikat i noen retning. Det gir
Utover dette er kartet uferdig. Vi vet ikke om . Vi vet ikke om . Én sammenheng er derimot lett å se: hvis , så er . Grunnen er at er lukket under komplement — snu bare svaret fra løsningsalgoritmen — så en likhet mellom og ville dratt begge klassene sammen.
Dette er ikke pynt. På eksamen kommer det som ja/nei-utsagn av typen «det er bevist at » (nei) eller « ligger i » (ja).
(Eksamensnivå.) Avgjør for hvert utsagn om det er sant eller usant, og begrunn med én setning.
a) .
b) Det er bevist at .
c) Et problem i har alltid et kort bevis for nei-svaret.
d) Hvis et problem ligger i , ligger komplementet også i .
e) Klassen inneholder bare problemer som er vanskelige å løse.
b) Usant. Spørsmålet er åpent. Vi vet bare at .
c) Usant. garanterer et kort bevis for ja-svaret. Korte bevis for nei-svaret er det handler om, og om de to klassene er like, er ukjent.
d) Sant. Kjør løsningsalgoritmen og snu svaret; det koster ett ekstra steg, så kjøretiden er fortsatt polynomisk.
e) Usant. ligger inne i , så alle de raskt løsbare problemene — sortering, korteste vei, maksimal flyt — ligger også i .
Formen er verdt å legge merke til: sant/usant først, deretter én setning. Ingen av delsvarene trenger mer.
Betrakt problemet «har grafen en hamiltonsykel?».
a) Formulér komplementproblemet.
b) Forklar hvorfor et sertifikat for det opprinnelige problemet er lett å oppgi, mens det ikke er opplagt hva et sertifikat for komplementet skulle være.
«Alle problemer i ligger både i og i .»
Definisjonen av krever at sertifikatet har polynomisk lengde i inputstørrelsen.
a) Forklar hvorfor kravet er nødvendig.
b) Beskriv hva som ville skjedd med definisjonen uten det.
Abstrakte og konkrete problemer (~5 min)
Dette avsnittet er kjenne til-stoff: det er randstoff i faget, og det er nok at du kjenner igjen ordene hvis de dukker opp i en oppgavetekst. Har du kort tid, hopp videre til begrepsbanken.
Så langt har vi snakket om «problemer» uten å si hva et problem er matematisk. Den presise varianten går slik. Et abstrakt problem er en tilordning fra instanser til svar — for et avgjørelsesproblem: fra hver instans til ja eller nei. Men en algoritme leser ikke abstrakte objekter; den leser en bitstreng. Derfor kodes instansen som en streng av symboler, og resultatet kalles et konkret problem. Da blir et avgjørelsesproblem det samme som mengden av alle strenger som koder en ja-instans, og en slik mengde kalles et formelt språk.
Det er derfor du kan se og definert som mengder av språk, og skrivemåten i stedet for «problemet ligger i ». Det er samme sak i annen drakt.
Hvorfor det er verdt fem minutter: kodingen er ikke uskyldig. Størrelsen er antall symboler i den kodede instansen, og et tall som skrives binært fyller langt færre symboler enn det samme tallet skrevet som en lang strek av ettall. Den forskjellen ser harmløs ut nå, men den er selve grunnen til at 0-1-ryggsekk kalles pseudopolynomisk i kap. 7.2.
b) «Et sertifikat for at grafen har en hamiltonsykel, er selve nodesekvensen.»
c) «Optimeringsproblemet ‘finn den korteste rundturen’ er et avgjørelsesproblem.»
d) «Størrelsen i uttrykket er antall objekter i inputen.»
Oppslagstabell: problemer vi vet ligger i P (~2 min)
Alle radene under er avgjørelsesvarianter av problemer du har møtt tidligere i boka. De ligger i fordi vi har en polynomisk algoritme som avgjør dem — og de ligger dermed også i .
| Problem (avgjørelsesvariant) | Algoritme som avgjør det | Kjøretid | Krav/egenskap |
|---|---|---|---|
Finnes en vei fra s til t? | BFS | ingen | |
Finnes en vei fra s til t med vekt høyst ? | Dijkstra | krever ikke-negative kantvekter | |
| Samme, med negative kanter tillatt | Bellman-Ford | oppdager negative sykler | |
| Finnes et spenntre med vekt høyst ? | MST-Kruskal | grafen må være sammenhengende | |
| Finnes en flyt med verdi minst ? | Edmonds-Karp | krever korteste forøkende sti | |
Er A[1..n] sortert stigende? | én gjennomgang | ingen | |
Kan A[1..n] sorteres på ? | Merge-Sort | ikke på stedet, stabil |
Poenget med tabellen er kontrasten som kommer: HAM-CYCLE, som du så i dette kapitlet, har ingen slik rad. Vi kan verifisere svaret i , men vi kjenner ingen polynomisk algoritme som finner det. Hvorfor det er slik — og hva vi likevel kan bevise — er kap. 7.2 og kap. 7.3.
Begrepsbank (~5 min)
Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.
Én konkret input til et problem: den bestemte grafen, den bestemte tallmengden, den bestemte avstandstabellen sammen med terskelen.
Problemet er regelen; instansen er tilfellet. Når vi skriver i definisjonene av , er en instans.
En instans der svaret på avgjørelsesproblemet er ja, kalles en ja-instans; er svaret nei, er det en nei-instans.
Skillet er verktøyet du bruker når du skal vise at en transformasjon mellom to problemer er riktig: den må sende ja-instanser til ja-instanser og nei-instanser til nei-instanser. Den egenskapen heter svarbevarende og er selve kjernen i kap. 7.2.
Antall symboler den kodede inputen fyller — ikke antall objekter i den.
For en graf gitt som nabomatrise er inputstørrelsen omtrent bits. For en liste med tall er den summen av tallenes bitlengder: tallet fyller bits. Skillet virker pedantisk til du møter et problem der kjøretiden avhenger av en tallverdi i inputen framfor av antall symboler — da bestemmer det alt.
Å prøve alle kandidatløsninger etter tur og se om noen holder. Kalles også brute force.
Uttømmende søk løser nesten alle problemene i dette kapitlet — bare altfor sakte. For hamiltonsykel i en graf med noder er det sekvenser; for en delmengde av tall er det delmengder. Med 5 tall er , med 50 tall er det over .
En kjøretid som vokser raskere enn ethvert polynom: , , .
Kontrasten til er skarpere enn tallene antyder. For er , mens overstiger — over ni milliarder ganger større. Det er derfor grensen mellom håndterbart og ikke settes ved polynomisk tid.
Den eldre definisjonen tenker seg en maskin som gjetter et sertifikat og deretter kontrollerer det i polynomisk tid. Den er likeverdig med verifikasjonsdefinisjonen, og verifikasjonsformen er den du skal kunne skrive ned. Feillesningen «N for not» er direkte årsak til den vanligste feilen på eksamen.
En tilordning fra instanser til svar, uten noen antagelse om hvordan instansen skrives ned. For et avgjørelsesproblem: fra hver instans til ja eller nei.
Nyttig å kjenne til, men randstoff i dette faget.
Et konkret problem er et abstrakt problem der instansene er kodet som strenger av symboler — det en algoritme faktisk kan lese.
Da blir et avgjørelsesproblem det samme som mengden av alle strenger som koder en ja-instans, og en slik mengde kalles et formelt språk, gjerne skrevet . Det er derfor du kan se og definert som mengder av språk og skrivemåten . Randstoff, men verdt å kjenne igjen.
Det åpne spørsmålet om alt som kan verifiseres raskt, også kan løses raskt.
Status i dag: er bevist og enkelt. Om inklusjonen er streng — altså om det finnes et problem i som ikke er i — vet ingen. Skriv aldri at er bevist, og skriv aldri at er bevist. Det eneste riktige svaret er at spørsmålet er åpent.
Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.
Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.