Vi har skrevet om effektive algoritmer for å løse komplekse problemer, som korteste vei, Euler graf, minimum spenner treet, etc. Det var alle suksesshistorier av algoritmedesignere. I dette innlegget diskuteres feilhistorier om datavitenskap.
Kan alle beregningsproblemer løses av en datamaskin? Det er beregningsproblemer som ikke kan løses av algoritmer selv med ubegrenset tid. For Eksempel Turing Halting problem (Gitt et program og en inngang, om programmet til slutt vil stoppe når det kjøres med den inngangen, eller vil kjøre for alltid). Alan Turing viste at generell algoritme for å løse stoppproblemet for alle mulige programinngangspar ikke kan eksistere. En viktig del av beviset er At Turing machine ble brukt som en matematisk definisjon av en datamaskin og et program (Source Halting Problem).
Status FOR Np Komplette problemer er en annen feilhistorie, NP komplette problemer er problemer hvis status er ukjent. Ingen polynomisk tidsalgoritme har ennå blitt oppdaget FOR NOE NP-komplett problem, og ingen har ennå kunnet bevise at ingen polynomisk tidsalgoritme eksisterer for noen av dem. Den interessante delen er, hvis NOEN av de np komplette problemene kan løses i polynomisk tid, så kan alle løses.
Hva ER NP, p, np-komplett og Np-Harde problemer?P Er et sett med problemer som kan løses av En Deterministisk Turingmaskin i Polynomisk Tid.NP er et sett med beslutningsproblemer som kan løses Av En Ikke-Deterministisk Turingmaskin i Polynomisk Tid. P er delmengde AV NP (ethvert problem som kan løses av deterministisk maskin i polynomisk tid kan også løses av ikke – deterministisk maskin i polynomisk tid).Uformelt er NP sett med beslutningsproblemer som kan løses med en polynomisk tid via En «Heldig Algoritme», en magisk algoritme som alltid gjør en riktig gjetning blant det gitte settet av valg (Kilde Ref 1).
np-komplette problemer er de vanskeligste problemene I NP-settet. Et beslutningsproblem L er np-komplett hvis:
1) L er I NP(Enhver løsning FOR np-komplette problemer kan verifiseres raskt, men det er ingen effektiv kjent løsning).2) Hvert problem i NP kan reduseres Til l i polynomisk tid (Reduksjon er definert nedenfor).
et problem ER NP-Hard hvis det følger eiendom 2 nevnt ovenfor, trenger ikke å følge eiendom 1. DERFOR ER Np-Complete set også en delmengde AV Np-Hard set.
Beslutning vs Optimaliseringsproblemer
NP-fullstendighet gjelder riket av beslutningsproblemer. Det ble satt opp på denne måten fordi det er lettere å sammenligne vanskeligheten med beslutningsproblemer enn optimaliseringsproblemer. I virkeligheten vil det å kunne løse et beslutningsproblem i polynomisk tid ofte tillate oss å løse det tilsvarende optimaliseringsproblemet i polynomisk tid (ved hjelp av et polynomalt antall anrop til beslutningsproblemet). Så, å diskutere vanskeligheten med beslutningsproblemer er ofte virkelig lik å diskutere vanskeligheten med optimaliseringsproblemer. (Kilde Ref 2).
for eksempel vurdere toppunktet dekke problemet (Gitt en graf, finne ut minimum størrelse toppunktet sett som dekker alle kanter). Det er et optimaliseringsproblem. Tilsvarende beslutningsproblem er, gitt urettet graf G Og k, er det et toppunktdeksel av størrelse k?
Hva Er Reduksjon?
La L1 og L2 være to beslutningsproblemer. Anta at algoritmen A2 løser L2. Det vil si at hvis y er en inngang For L2, vil algoritme A2 svare Ja eller Nei, avhengig av om y tilhører L2 eller ikke.ideen er å finne en transformasjon Fra L1 Til L2 slik at algoritmen A2 kan være en del av en algoritme A1 for å løse L1.
Læringsreduksjon generelt er svært viktig. For eksempel, hvis vi har biblioteksfunksjoner for å løse et bestemt problem, og hvis vi kan redusere et nytt problem til et av de løste problemene, sparer vi mye tid. Tenk på eksemplet på et problem der vi må finne minimum produktbane i en gitt rettet graf hvor produkt av bane er multiplikasjon av vekter av kanter langs banen. Hvis Vi har kode For dijkstras algoritme for å finne korteste vei, kan vi ta logg over alle vekter og bruke Dijkstras algoritme for å finne minimumsproduktbanen i stedet for å skrive en ny kode for dette nye problemet.
hvordan bevise at et gitt problem er np fullført?fra definisjonen AV np-complete virker det umulig å bevise at et problem L er NP-Complete. Per definisjon krever det at vi viser at hvert problem I NP er polynomisk tid reduseres Til L. Heldigvis er Det en alternativ måte å bevise det på. Tanken er å ta et kjent Np-Komplett problem og redusere Det Til L. Hvis polynomisk tidsreduksjon er mulig, kan Vi bevise At L er Np-Komplett ved transitivitet av reduksjon (Hvis ET Np-Komplett problem kan reduseres Til L i polynomisk tid, så kan alle problemer reduseres Til L i polynomisk tid).
Hva var det første problemet som viste SEG SOM Np-Complete?det må være noen første Np-Komplett problem bevist per definisjon AV Np-Komplette problemer. SAT (Boolsk satisfiability problem) er det første Np-Komplette problemet bevist Av Cook (Se CLRS bok for bevis).
DET er alltid nyttig å vite OM Np-Fullstendighet selv for ingeniører. Anta at du blir bedt om å skrive en effektiv algoritme for å løse et ekstremt viktig problem for din bedrift. Etter mye tenkning, kan du bare komme opp eksponentiell tid tilnærming som er upraktisk. Hvis du ikke vet OM NP-Fullstendighet, kan du bare si at jeg ikke kunne komme med en effektiv algoritme. Hvis DU vet OM NP-Fullstendighet og bevise at problemet SOM NP-complete, kan du stolt si at polynomisk tidsløsning er usannsynlig å eksistere. Hvis det er en polynomisk tidsløsning mulig, løser den løsningen et stort problem med datavitenskap mange forskere har prøvd i årevis.
Vi vil snart diskutere FLERE Np-Komplette problemer og deres bevis FOR NP-Fullstendighet.