olemme kirjoittaneet tehokkaista algoritmeista monimutkaisten ongelmien ratkaisemiseksi, kuten lyhin polku, Eulerin kuvaaja, minimi spanning tree jne. Ne olivat algoritmisuunnittelijoiden menestystarinoita. Tässä viestissä käsitellään tietojenkäsittelytieteen epäonnistumistarinoita.
Voiko tietokone ratkaista kaikki laskennalliset ongelmat? On laskennallisia ongelmia, joita algoritmit eivät voi ratkaista edes rajattomasti aikaa. Esimerkiksi Turing pysäyttäminen ongelma (koska ohjelma ja tulo, onko ohjelma lopulta pysäyttää, kun ajaa, että tulo, tai ajaa ikuisesti). Alan Turing todisti, että yleistä algoritmia pysäyttämisongelman ratkaisemiseksi kaikille mahdollisille ohjelman syöttöpareille ei voi olla olemassa. Keskeinen osa todistusta on, että Turingin konetta käytettiin tietokoneen ja ohjelman matemaattisena määritelmänä (Source pysäytysongelma).
Status of NP Complete problems on toinen epäonnistumistarina, NP complete problems ovat ongelmia, joiden tila on tuntematon. Mitään polynomin aika-algoritmia ei ole vielä löydetty yhdellekään NP: n täydelliselle ongelmalle, eikä kukaan ole vielä kyennyt todistamaan, että yhdellekään niistä ei ole olemassa polynomin aika-algoritmia. Mielenkiintoinen osa on, jos jokin NP täydellinen ongelmia voidaan ratkaista polynomi aika, niin ne kaikki voidaan ratkaista.
Mitä ovat NP, P, NP-complete ja NP-Hard problems?
P on joukko ongelmia, jotka voidaan ratkaista deterministisellä Turingin koneella Polynomiajalla.
NP on joukko ratkaisuongelmia, jotka voidaan ratkaista ei-deterministisellä Turingin koneella Polynomiajalla. P on NP: n osajoukko (mikä tahansa ongelma, joka voidaan ratkaista deterministisellä koneella polynomin ajassa, voidaan ratkaista myös ei-deterministisellä koneella polynomin ajassa).
epävirallisesti NP on joukko ratkaisuongelmia, jotka voidaan ratkaista polynomin ajan avulla ”onnekkaalla algoritmilla”, maagisella algoritmilla, joka tekee aina oikean arvauksen annettujen valintojen joukosta (Lähdeviittaus 1).
NP-täydelliset ongelmat ovat NP-joukon vaikeimpia ongelmia. Päätösongelma L on NP-täydellinen, jos:
1) L on NP: ssä (mikä tahansa tietty ratkaisu NP-täydellisiin ongelmiin voidaan todentaa nopeasti, mutta tehokasta tunnettua ratkaisua ei ole).
2) Jokainen NP: n ongelma on redusoitavissa L: ksi polynomiajassa (reduktio määritellään jäljempänä).
ongelma on NP-vaikea, jos se noudattaa edellä mainittua ominaisuutta 2, ei tarvitse noudattaa ominaisuutta 1. Siksi NP-täydellinen joukko on myös NP-kovan joukon osajoukko.
päätös vs Optimointiongelmat
NP-täydellisyys koskee päätöksenteko-ongelmia. Se perustettiin tällä tavalla, koska se on helpompi verrata vaikeus päätöksenteko ongelmia kuin optimointi ongelmia. Todellisuudessa kuitenkin se, että pystytään ratkaisemaan päätösongelma polynomiajalla, antaa meille usein mahdollisuuden ratkaista vastaava optimointiongelma polynomiajalla (käyttämällä polynomien määrää päätöksiongelmaan). Niinpä päätöksenteko-ongelmien vaikeudesta keskusteleminen on usein oikeastaan samaa kuin optimointiongelmien vaikeudesta keskusteleminen. (Lähdeviittaus 2).
esimerkiksi tarkastellaan huippupiste kansi ongelma (koska graafi, selvittää vähimmäiskokoisen huippupiste joukko, joka kattaa kaikki reunat). Se on optimointiongelma. Vastaava päätös ongelma on, koska ohjaamaton kuvaaja G ja k, on olemassa huippupiste kattaa koko k?
mitä vähennys on?
olkoon L1 ja L2 kaksi päätösongelmaa. Oletetaan, että algoritmi A2 ratkaisee L2: n. Toisin sanoen, jos y on tulo L2 sitten algoritmi A2 vastaa kyllä tai ei riippuen siitä, onko y kuuluu L2 vai ei.
ideana on löytää muunnos L1: stä L2: een niin, että algoritmi A2 voi olla osa algoritmia A1 L1: n ratkaisemiseksi.
ylipäätään oppimisen vähentäminen on erittäin tärkeää. Jos meillä on esimerkiksi kirjastotoimintoja tietyn ongelman ratkaisemiseksi ja jos voimme vähentää uuden ongelman johonkin ratkaistuista ongelmista, säästämme paljon aikaa. Harkitse esimerkki ongelma, jossa meidän on löydettävä vähintään tuotteen polku tietyn suunnattu kuvaaja, jossa tuote polku on kertolasku painot reunojen pitkin polkua. Jos meillä on koodi Dijkstran algoritmi löytää lyhin polku, voimme ottaa loki kaikki painot ja käyttää Dijkstran algoritmi löytää minimituotepolku sijaan kirjoittaa tuoretta koodia tähän uuteen ongelmaan.
Miten todistaa, että annettu ongelma on NP täydellinen?
NP-complete-määritelmän perusteella näyttää mahdottomalta todistaa, että ongelma L on NP-Complete. Määritelmän mukaan se vaatii meitä, että näyttää jokainen ongelma NP on polynomi aika reducible L. onneksi on vaihtoehtoinen tapa todistaa se. Ajatuksena on ottaa tunnettu NP-täydellinen ongelma ja vähentää se L. Jos polynomi aika reduction on mahdollista, voimme todistaa, että L on NP-täydellinen Transitiivisuus reduction (jos NP-täydellinen ongelma on reducible l polynomi aika, sitten kaikki ongelmat ovat reducible l polynomi aika).
mikä oli ensimmäinen NP-täydelliseksi osoittautunut ongelma?
täytyy olla jokin ensimmäinen NP-täydellinen ongelma, joka on todistettu NP-täydellisten ongelmien määritelmällä. SAT (Boolean satisficibility problem) on ensimmäinen Cookin todistama NP-täydellinen ongelma (katso clrs book for proof).
on aina hyödyllistä tietää NP-täydellisyydestä myös insinööreille. Oletetaan, että sinua pyydetään kirjoittamaan tehokas algoritmi yrityksellesi erittäin tärkeän ongelman ratkaisemiseksi. Kun paljon ajattelua, voit vain keksiä eksponentiaalinen aika lähestymistapa, joka on epäkäytännöllinen. Jos et tiedä NP-täydellisyydestä, voit vain sanoa, etten voinut tulla tehokkaan algoritmin kanssa. Jos tiedät NP-täydellisyydestä ja todistat, että ongelma on NP-täydellinen, voit ylpeänä sanoa, että polynomin aikaratkaisua ei todennäköisesti ole olemassa. Jos on olemassa polynomi aika ratkaisu mahdollista, niin että ratkaisu ratkaisee suuri ongelma tietojenkäsittelytieteen monet tutkijat ovat yrittäneet vuosia.
alamme pian keskustella enemmän NP-täydellisistä ongelmista ja niiden todisteista NP-täydellisyyden puolesta.