Tietojenkäsittelytieteen suurin ongelma: P vs. NP

On olemassa seitsemän matemaattista ongelmaa, jotka Clayn matematiikkainstituutti on julistanut niin vaikeiksi ja mielenkiintoisiksi, että se on nimennyt ne vuosituhannen ongelmiksi, ja jokaisen ratkaisemisesta ratkaisija saa miljoonan dollarin palkinnon. Yksi ongelmista liittyy myös tietojenkäsittelytieteeseen, ja sitä kutsutaan P vs. NP -ongelmaksi. Selvitetään, mistä tässä ongelmassa oikeastaan on kyse.

No niin. Ei kannata kuvitella, että tämän selittäminen olisi helppoa. Kyseessä on kuitenkin vuosituhannen ongelma. Mene siis keittämään hyvää vihreää teetä 🍵 ja aloitetaan. Ensin tarkastellaan neljää eri ongelmaa tietojenkäsittelyn ja algoritmien maailmasta. Analysoidaan ongelmat ja katsotaan, miten ne liittyvät kirjaimiin P ja NP.

Ongelma 1: pienimmän luvun löytäminen

P vs. NP liittyy algoritmeihin ja niiden kompleksisuuteen. Kuvittele, että kaataisin eteesi sata paperilappua, joista jokaiseen on kirjoitettu yksi luku, ja pyytäisin sinua löytämään lapun, jossa on pienin luku. Kuinka kauan siihen kuluu aikaa?

Puoli minuuttia? Kaksi minuuttia?

Nämä ovat aikayksiköitä, jotka eivät teoreettisessa tietojenkäsittelytieteessä kiinnosta kovin paljon. Kiinnostavaa on pikemminkin operaatioiden määrä. Voidaan siis kysyä vähän toisin: kuinka monta lappua täytyy tarkistaa, jotta voi olla varma pienimmän luvun löytymisestä? Vastaus on, että kaikki laput täytyy tarkistaa — sillä pienin luku voi olla aivan viimeisessä lapussa. Kun eteesi heitetään sata lappua, sinun täytyy tarkistaa sata lappua. Jos eteesi heitetään tuhat, täytyy tarkistaa tuhat. Yleisesti, kun eteesi heitetään n lappua, täytyy tarkistaa n lappua.

Tätä kutsutaan algoritmien kompleksisuudeksi. Jos eteesi heitetään n lappua ja sinun täytyy tehdä n operaatiota pienimmän luvun löytämiseksi, tämän pienimmän luvun etsintäalgoritmin kompleksisuus on n. Sitä kutsutaan myös lineaariseksi kompleksisuudeksi, koska kompleksisuutta kuvaa lineaarinen funktio.

Hyvä on, kävit läpi sata lappua ja ilmoitit, että pienin luku on 17. Miten voin tarkistaa, että puhut totta? Ei ole muuta tapaa kuin käydä taas kaikki laput läpi ja tarkistaa, ettei yhdessäkään ole pienempää lukua. Sinun täytyi siis katsoa n lappua löytääksesi pienimmän luvun, ja minun täytyy tarkistuksessa tehdä sama. Tuloksen tarkistamisen kompleksisuus on siis myös n, lineaarinen kompleksisuus.

Onko olemassa algoritmeja, joissa tulos on helpompi tarkistaa kuin löytää?

Ongelma 2: parin tulo

Kuvittele, että kaadan eteesi kaksi yhtä suurta paperilappupinoa, ja jokaisessa lapussa on taas yksi luku. Nyt pyytäisin sinua etsimään pinosta A luvun ja pinosta B luvun niin, että niiden tulo on 918. Esimerkiksi olkoot lukupinot seuraavat:

$$\begin{array}{rcl}A& =& \{49,11,32,54,15\}\\ B& =& \{17,64,74,61,21\}\end{array}$$

Miten löydetään lukupari, jonka tulo on 918? Voidaan yksinkertaisesti kokeilla kaikkia mahdollisuuksia. Kuinka monta niitä on? Aika paljon, niitä on 25. Aloitetaan kertomalla pinon A ensimmäinen luku, eli 49, jokaisella pinon B luvulla:

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Mikään lukupari ei anna tulokseksi 918. Kokeillaan siis samaa pinon A muille luvuille, eli vielä viisi paria luvulle 11, viisi paria luvulle 32, viisi paria luvulle 54 ja viimeiset viisi paria luvulle 15. Yhteensä voidaan kokeilla 25 lukuparia. Lopulta huomataan, että 54 · 17 = 918.

Mikä on tämän algoritmin kompleksisuus? Kiinnostavaa on, kuinka monta lukuparia jouduttiin kertomaan keskenään. Kummassakin pinossa oli viisi lappua, ja jouduttiin kokeilemaan jokaista ensimmäisen pinon viidestä luvusta jokaisen toisen pinon viiden luvun kanssa. Yhteensä kokeiltiin 5 · 5 = 25 yhdistelmää. Jos eteesi heitettäisiin kaksi 10 lapun pinoa, jouduttaisiin kokeilemaan 10 · 10 = 100 yhdistelmää. Yleistämällä: jos eteesi heitetään kaksi n lapun pinoa, täytyy kokeilla n · n = n² yhdistelmää.

Sanotaan, että tämän algoritmin kompleksisuus on n², neliöllinen kompleksisuus, koska sitä kuvaa toisen asteen polynomifunktio.

Kuinka vaikeaa tuloksen tarkistaminen sitten on? Jos vastaat minulle, että 54 ja 17 ovat luvut, joiden tulo on 918, minun ei tarvitse käydä läpi kaikkia kummastakin pinosta muodostuvia lukupareja, kuten sinun piti tehdä. Riittää, että kerron keskenään tämän yhden parin 54 · 17, ja tiedän, onko sinulla oikea vastaus vai ei. Siinä missä tämän ongelman ratkaisemiseen täytyy laskea jopa n² tuloa, tarkistamiseen riittää laskea vain yksi tulo. Tarkistuksen kompleksisuus on siis vakio 1.

Tässä tämä tehtävä eroaa selvästi edellisestä, jossa varsinaiseen laskemiseen ja sitä seuranneeseen tarkistukseen tarvittiin yhtä monta askelta.

Tämä tehtävä on myös suuruusluokaltaan vaikeampi kuin edellinen. Jos kaataisin eteesi kymmenentuhatta lappua ja pyytäisin löytämään pienimmän luvun, löytäisit sen luultavasti yhdessä päivässä. Mutta jos kaataisin eteesi kaksi kertaa kymmenentuhatta lappua ja antaisin sinun etsiä tulon, sinun pitäisi tarkistaa kymmenentuhatta kertaa kymmenentuhatta tuloa, eli sata miljoonaa laskutoimitusta. Vaikka kokeilisit yhden tulon sekunnissa, siihen menisi noin kolme vuotta.

Ongelma 3: osajoukon summa

Katsotaan kolmatta ongelmaa. Tällä kertaa kaadan eteesi kaksitoista lukulappua ja pyydän sinua löytämään mielivaltaisen määrän lappuja, joiden summa on nolla. Esimerkiksi:

$$A=\{24,-69,1,-15,-76,-60,16,-83,48,-22,54,-47\}$$

Valitse näistä luvuista mikä tahansa ryhmä, jonka summa on 0. Esimerkiksi luvut

$$24+48-69+1$$

antavat summaksi 4, joten ne eivät ole oikea vastaus. Oikea vastaus on ryhmä lukuja… ja tiedätkö mitä? Yritä löytää se itse kotitehtävänä 😉. On olemassa vain yksi ryhmä lukuja, joiden summa on 0. Ainakin pääset kokeilemaan, kuinka vaikea tämä ongelma on.

Nyt täytyy tietää tämän ongelman kompleksisuus. Itse laskeminen ei ole ihan triviaali, ja se on enemmän herkkusuille. Jos siis kiinnostaa, miten tämän ongelman kompleksisuus lasketaan, jatka lukemista. Muuten voit hypätä seuraavaan lukuun. ⏩

Miten siis löydetään lukuryhmä, jonka summa on 0? No, täytyy yksinkertaisesti kokeilla kaikkia mahdollisia lukujen kombinaatioita. Täytyy kokeilla kaikki lukuparit, kaikki kolmikot, neljän ryhmät, viiden ryhmät ja niin edelleen, ja jokaisesta ryhmästä täytyy tarkistaa, onko sen summa nolla. Kuinka monta tällaista kombinaatiota on?

Katsotaan asiaa pienemmällä lukujoukolla. Kuinka monta eri lukuryhmää eli osajoukkoa voidaan muodostaa kolmen luvun joukosta B = {5, 7, 9}? Niitä on yhteensä kahdeksan:

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5,9\}\\ B_6& =& \{5,7\}\\ B_7& =& \{7,9\}\\ B_8& =& \{5,7,9\}\end{array}$$

Huomaa, että myös tyhjä osajoukko B₁ laskettiin mukaan. Siitä ei ole nyt kovin paljon hyötyä, mutta järjestyksen vuoksi se jätettiin mukaan. Laskennan yksinkertaistamiseksi jokaiselle osajoukolle liitetään binäärivektori. Binäärivektori on yksinkertaisesti nollien ja ykkösten jono, esimerkiksi 00101010. Käytetään tässä kolmen pituisia binäärivektoreita. Vektori liitetään niin, että 101 liitetään osajoukolle, joka sisältää ”alkuperäisen joukon ensimmäisen ja kolmannen luvun mutta ei toista lukua”, eli joukolle {5, 9}. Vektori 110 liitetään osajoukolle, joka sisältää ”alkuperäisen joukon ensimmäisen ja toisen luvun mutta ei kolmatta”, eli joukolle {5, 7}, ja niin edelleen.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5,9\}& \to & 101\\ B_6=\{5,7\}& \to & 110\\ B_7=\{7,9\}& \to & 011\\ B_8=\{5,7,9\}& \to & 111\end{array}$$

Nähdään, että jokaisella osajoukolla on täsmälleen yksi kolmen pituinen binäärivektori. Ja jokainen kolmen pituinen binäärivektori vastaa täsmälleen yhtä osajoukkoa. Jos siis lasketaan, kuinka monta erilaista n:n pituista binäärivektoria on olemassa, saadaan niiden kombinaatioiden määrä, jotka voidaan muodostaa, kun syötteenä on n eri lukua. Lasketaan se.

Yhden pituisia binäärivektoreita on kaksi: 0 ja 1.

Kahden pituiset binäärivektorit saadaan niin, että otetaan kaikki yhden pituiset binäärivektorit ja lisätään jokaisen vektorin loppuun 0: saadaan vektorit 00 ja 10. Otetaan taas kaikki yhden pituiset vektorit ja lisätään loppuun 1: 01 ja 11. Näin saatiin kaikki kahden pituiset vektorit: 00, 01, 10 ja 11.

Kolmen pituiset binäärivektorit saadaan niin, että otetaan kaikki kahden pituiset binäärivektorit ja lisätään loppuun nolla: 000, 010, 100 ja 110, sekä ykkönen: 001, 011, 101 ja 111.

Ja niin edelleen jokaiselle seuraavalle pituudelle. Nähdään, että kun binäärivektorin pituutta kasvatetaan yhdellä, erilaisten binäärivektorien määrä kaksinkertaistuu. Neljän pituisia vektoreita saataisiin siis yhteensä 2 · 2 · 2 · 2, eli 16 erilaista kombinaatiota.

Yleisesti voidaan johtaa, että jos joukossa M on n alkiota, tämän joukon M kaikkien osajoukkojen määrä on yhtä suuri kuin kaikkien n:n pituisten binäärivektorien määrä, ja se on

$$\underset{n\text{ kertaa}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

2ⁿ vai n² — eikö se ole yks lysti? 🤷‍♂

Erilaisia osajoukkoja, jotka voidaan muodostaa n luvun joukosta, on siis 2ⁿ. Tässä tapauksessa lukuja on n = 12, joten täytyy tarkistaa 2¹² eri kombinaatiota, mikä on 4096 kombinaatiota. Sanotaan, että tämän ongelman kompleksisuus on 2ⁿ, eksponentiaalinen kompleksisuus, koska sitä kuvaa eksponenttifunktio.

Huomaa, että edellisen ongelman kompleksisuus oli n², kun taas tämän on 2ⁿ. Näyttää hyvin samanlaiselta, eikö niin? Mutta on suuri ero siinä, onko eksponentti vakio vai onko siinä muuttuja n. Huomaa, että kun n = 4, saadaan

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Hyvä on, toistaiseksi saadaan sama tulos. Entä kun n = 10?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Hups, eksponenttifunktio ampaisi ja on yhtäkkiä noin kymmenkertainen toisen asteen funktioon verrattuna. Mitä saadaan, kun n = 20?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1048576\end{array}$$

Eksponentiaalisen kompleksisuuden arvo on, kun n = 20, noin 2 600 kertaa suurempi kuin neliöllisen kompleksisuuden. Nähdään siis, että eksponenttifunktio kasvaa paljon nopeammin kuin toisen asteen polynomifunktio. Muista tämä, kun seuraava pandemia iskee ja leviää väestössä eksponentiaalisella vauhdilla.

Jos siis heittäisin eteesi kaksikymmentä lappua, sinun täytyisi tarkistaa 1 048 576 kombinaatiota. Se on aika paljon.

Miten tuloksen oikeellisuus tarkistetaan?

Kuinka kauan minulta kestää tarkistaa, että löytynyt lukuryhmä todella antaa summaksi 0? Se on melko nopeaa: laskan yksinkertaisesti yhteen tämän yhden lukuryhmän, ja jos sen summa on 0, olet löytänyt oikean lappuryhmän, ja jos summa on jokin muu, löysit väärän lappuryhmän.

Nähdään taas, että tuloksen tarkistaminen on suuruusluokaltaan helpompaa kuin sen löytäminen.

Ongelma 4: kauppamatkustajan ongelma

Kauppamatkustajan ongelma on yksi kuuluisimmista algoritmisista ongelmista. Karkeasti sanottuna on kauppamatkustaja, joka myy sadetta. Tämän kauppamatkustajan täytyy matkustaa paljon ansaitakseen elantonsa. Hän on siksi päättänyt käydä jokaisessa Tšekin tasavallan maakuntakeskuksessa. Koska hän ei halua tuhlata, hän on päättänyt löytää lyhimmän mahdollisen reitin, joka vie hänet kaikkien maan maakuntakeskusten kautta. Tehtävänä on löytää tällainen lyhin reitti.

Miten tämä lyhin reitti voidaan löytää? Kokeillaan kaikki mahdollisuudet.

Asiaa voi yksinkertaistaa. Kuvitellaan, että jokaisen kahden maakuntakeskuksen välillä on täsmälleen yksi lyhin reitti. Miten lyhin reitti löydetään kaikkien kaupunkien välillä? Maakuntakeskuksia on 14. Aloituspaikkaa on siis 14 vaihtoehtoa. Oletetaan, että aloitettiin Ostravasta!!! Minne Ostravasta voidaan päästä? Teoriassa voidaan matkustaa mihin tahansa muuhun maakuntakeskukseen. Valittavana on siis 13 jäljellä olevaa kaupunkia.

Jo nyt voidaan laskea, että kahdessa ensimmäisessä maakuntakeskuksessa käymiseen on yhteensä 14 · 13 mahdollisuutta — aloituspaikkaan on 14 vaihtoehtoa, ja sen jälkeen valittavana on 13 jäljellä olevaa maakuntakeskusta.

Kun saavutaan toiseen kaupunkiin, täytyy jatkaa eteenpäin. Kahdessa kaupungissa on jo käyty, joten voidaan matkustaa johonkin 12 jäljellä olevasta kaupungista. Kolmessa ensimmäisessä kaupungissa käymiseen on näin yhteensä 14 · 13 · 12 mahdollisuutta.

Kun kolmas maakuntakeskus on käyty, täytyy valita yksi 11 jäljellä olevasta kaupungista, sitten yksi 10 jäljellä olevasta kaupungista ja niin edelleen.

Kun kaikissa on käyty, huomataan, että valittavana oli yhteensä

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

vaihtoehtoa. Tämä voi muistuttaa kertomaa, jonka merkki on huutomerkki. Voidaan siis sanoa, että tämä tulo on 14!:

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

ja siis on olemassa 14! reittiä, jotka kulkevat Tšekin tasavallan kaikkien maakuntakeskusten kautta. Onko se paljon? Aika lailla, sillä

$$14!=87178291200.$$

Yleisesti, jos etsittäisiin lyhintä reittiä n kaupungin välillä, jouduttaisiin kokeilemaan n! eri reittiä. Tämän ratkaisun kompleksisuus on siis n!.

Miten tarkistettaisiin, että löydetty tulos on oikea? Jos kertoisit minulle, että lyhin reitti kulkee Plzeňistä Ostravaan, sitten Brnoon ja niin edelleen, miten voin tarkistaa, että puhut totta? No, se on aika vaikeaa 🤷‍♂. Kun katson reittiä, minulla ei ole helppoa tapaa tarkistaa, onko juuri tämä reitti lyhin. Minun täytyy oikeastaan tehdä koko laskenta uudelleen. Tuloksen tarkistamisen kompleksisuus on siis myös n!.

Luokat P ja NP

Esiteltiin neljä ongelmaa ja niitä ratkaisevat algoritmit, ja analysoitiin, kuinka vaikeaa ratkaisun löytäminen on ja kuinka vaikeaa tämän ratkaisun tarkistaminen on. Yhteenveto on tässä taulukossa:

Jaetaan nyt ongelmat kahteen ryhmään. Ensimmäisen ryhmän muodostavat ongelmat, jotka ovat helppoja ratkaista. Ne ovat ongelmia, jotka voidaan ratkaista kompleksisuudella n tai n² tai n³ tai n⁴ ja niin edelleen. Koska lausekkeita kuten n² kutsutaan polynomeiksi, tätä ongelmien luokkaa merkitään kirjaimella P. Sanotaan siis, että luokka P sisältää ongelmat, jotka voidaan ratkaista polynomiajassa (= kompleksisuus on vaikkapa n² tai n⁷). Yleisesti ne ovat ongelmia, jotka voidaan ratkaista enemmän tai vähemmän helposti.

Luokkaan P kuuluu siis ongelma 1, pienimmän luvun löytäminen, koska sen ratkaisun kompleksisuus on n, ja sinne kuuluu myös ongelma 2, parin tulo, koska sen ratkaisun kompleksisuus on n², jotka molemmat ovat polynomeja.

Toinen luokka on luokka NP. Se sisältää ongelmat, jotka voidaan tarkistaa polynomiajassa. Luokkaan NP kuuluvat siis kaikki ongelmat paitsi viimeinen. Kauppamatkustajan ongelmaa ei osata tarkistaa polynomiajassa. Edelliset kolme ongelmaa voidaan tarkistaa polynomiajassa.

Kauppamatkustajan ongelmaa ei osata ratkaista eikä tarkistaa polynomiajassa. Kauppamatkustajan ongelmalle tarvittaisiin siis vielä toinen luokka, joka sisältäisi vielä vaikeampia ongelmia. Tällainen luokka on olemassa, mutta se ei ole tässä vaiheessa kiinnostava.

On selvää, että luokka P on luokan NP osajoukko. Eli jokainen ongelma, joka on luokassa P, on samalla luokassa NP. Se on järkevää — jos jokin ongelma osataan ratkaista polynomiajassa, tulos osataan myös tarkistaa polynomiajassa.

P vs. NP -ongelma

Päteekö sama myös toisin päin? Onko jokainen luokan NP ongelma samalla myös luokassa P? Eli jos ongelman tulos voidaan tarkistaa polynomiajassa, onko olemassa myös algoritmi, joka ratkaisisi kyseisen ongelman polynomiajassa?

Esimerkiksi tiedetään, että ongelman 3, osajoukon summan, tulos voidaan tarkistaa polynomiajassa. Mutta sen ratkaisemiseen käytettiin algoritmia, joka ei ole polynomiaikainen: käytetyn algoritmin kompleksisuus on eksponentiaalinen, 2ⁿ. Mutta tiedetäänkö varmasti, ettei tälle ongelmalle ole olemassa mitään polynomisen kompleksisuuden algoritmia?

Ei tiedetä!

Hyvin voisi käydä niin, että jokaiselle ongelmalle, joka voidaan tarkistaa polynomiajassa, on olemassa algoritmi, joka ratkaisee ongelman polynomiajassa. Sitä ei tiedetä. Tällaisen algoritmin olemassaoloa ei osata todistaa, mutta sen olemassaoloa ei osata myöskään kumota.

Jos jokaiselle luokan NP ongelmalle olisi olemassa algoritmi, joka ratkaisee sen polynomiajassa, se tarkoittaisi, että luokka NP olisi itse asiassa sama kuin luokka P. Kaikki luokan P ongelmat olisivat luokassa NP ja kaikki luokan NP ongelmat olisivat luokassa P — luokat olisivat samat, identtiset.

P vs. NP -ongelma on siis kysymys siitä, onko luokka P sama kuin luokka NP vai onko kyseessä kaksi eri ongelmaluokkaa.

Joko siis pätee P = NP tai pätee P ≠ NP. Sitä ei kukaan tiedä, ja jos keksit vastauksen, odottaa miljoonan dollarin palkinto, kuolematon maine ja todennäköisesti myös Turingin palkinto, joka on tietojenkäsittelytieteilijöiden Nobel.

Mitä tapahtuisi, jos P = NP?

Mitä tapahtuisi, jos pätisi P = NP? No, ei ole ihan helppoa sanoa, mitä tapahtuisi. Tiedettäisiin, että kaikille luokan NP ongelmille on olemassa algoritmi, joka ratkaisee ne polynomiajassa. Esimerkiksi että ongelmalle 3, osajoukon summalle, on olemassa algoritmi, joka ratkaisee sen polynomiajassa. Tässä on kuitenkin kolme muttaa:

• Se, että tiedettäisiin tällaisen algoritmin olevan olemassa, ei tarkoita, että sellainen osattaisiin löytää. Tiedettäisiin vain, että kyllä, on olemassa algoritmi, joka ratkaisee ongelman polynomiajassa, mutta sitä ei ehkä osattaisi rakentaa vielä sataan vuoteen. Se on jotain samankaltaista kuin se, että yleinen suhteellisuusteoria ennusti mustien aukkojen olemassaolon, mutta silti meni vielä useita vuosikymmeniä, ennen kuin onnistuttiin ottamaan ensimmäinen ”valokuva” mustasta aukosta.
• Se, että on olemassa polynomiajassa toimiva algoritmi, ei valitettavasti vielä tarkoita, että se on nopea. Voitaisiin löytää algoritmi, jonka kompleksisuus on n¹⁰⁰. Lauseke n¹⁰⁰ on nimittäin myös polynomi. Kun verrataan kompleksisuuksia 2ⁿ ja n¹⁰⁰, huomataan, että niin kauan kuin n on suhteellisen pieni, algoritmi, jonka kompleksisuus on 2ⁿ, tarvitsee silti vähemmän operaatioita. Esimerkiksi kun n = 20, pätee 2²⁰ = 1 048 576, kun taas lauseke 20¹⁰⁰ johtaa lukuun, jossa on noin 130 numeroa, ja se on 120 kertaluokkaa suurempi kuin 1 048 576. Tällainen polynomiaikainen algoritmi olisi siis käytännössä hitaampi kuin eksponentiaalinen. Ainakin niin kauan kuin n on suhteellisen pieni.
• Jos sittenkin onnistuttaisiin löytämään nopea polynomiajassa toimiva algoritmi, voitaisiin ratkaista paljon ongelmia nopeammin ja tarkemmin. Se on tietysti myönteinen uutinen, mutta sillä on myös kielteiset puolensa. On ala, joka luottaa siihen, että jotkin ongelmat ovat vaikeasti ratkaistavia, ja se on kryptografia — salaus. Voisi siis käydä niin, että nykyisten salausten murtaminen olisi suuruusluokaltaan helpompaa.

Välihuomautus: koska luit tänne asti, paljastan palkinnoksi, että ongelman 3 ratkaisu on 24 + 1 − 60 + 16 − 83 + 48 + 54.

Mitä tapahtuisi, jos P ≠ NP?

Jos ongelmaluokat P ja NP olisivat erilaiset, ei tapahtuisi kovin paljon, koska se on enemmän tai vähemmän vallitseva tilanne. Tällä hetkellä ei tunneta algoritmia, joka ratkaisisi jonkin vaikean luokan NP ongelman polynomiajassa, ja jos joku todistaisi, että P ≠ NP, asia pysyisi vain ikuisesti sellaisena. Paljon suurempi sensaatio olisi todistus siitä, että P = NP.

Viittauksia populaarikulttuurissa

• Eräässä Simpsonit-sarjan jaksossa nähdään, että Homer päätyy jonkinlaiseen vaihtoehtoiseen todellisuuteen, jossa hänelle paljastuu, että P = NP. Nähtävissä osoitteessa youtube.com.
• Futuramassa taas nähdään, että varastossa on kaksi kansiota, toisessa nimi P ja toisessa nimi NP. Nähtävissä osoitteessa youtube.com.
• Elementary-sarjan toisen kauden toinen jakso, ”Solve for X”, käsitteli sellaisen matemaatikon murhaa, joka oli todennäköisesti ratkaissut P vs. NP -ongelman.