Oletko koskaan miettinyt: Mikä on laite, jolla luet tätä artikkelia? Mikä on tietokone? Tietojenkäsittelytiede juontaa juurensa kauan ennen näiden nykyaikaisten tietokonelaitteiden ajattelua. Alalla, jossa yleisimmin kysytyt kysymykset liittyvät ohjelmointikieliin, kehyksiin ja kirjastoihin, otamme usein peruskäsitteet, jotka tekevät tietokoneesta itsestäänselvyytenä.

Mutta näillä tietokoneilla, joilla näyttää olevan ääretön potentiaali - onko niillä rajoituksia? Onko ongelmia, joita tietokoneet eivät pysty ratkaisemaan?

Tässä artikkelissa käsittelemme näitä kysymyksiä siirtymällä pois ohjelmointikielten ja tietokonearkkitehtuurien yksityiskohdista. Ymmärtämällä tietokoneiden ja algoritmien tehon ja rajoitukset voimme parantaa ajattelutapojamme ja perustella paremmin strategioita.

Abstrakti näkymä tietojenkäsittelystä tuottaa tuloksia, jotka ovat kestäneet ajan koetuksen ja ovat yhtä arvokkaita meille tänään kuin ne olivat, kun ne kehitettiin ensimmäisen kerran 1970-luvulla.

Computabilidad

Mikä on tietokone? Mikä on ongelma?

Koulussa meille opetetaan usein ongelmien ja toimintojen henkinen malli, joka kertoo jotain tältä:

Funktio on toimenpide, jota syötät tuloon x löytääksesi lähdön f (x).

On käynyt ilmi, että matemaattinen määritelmä on erilainen:

Funktio on joukko pareja, jotka on järjestetty siten, että kunkin parin ensimmäinen elementti tulee joukosta X (kutsutaan toimialueeksi), kunkin parin toinen elementti tulee joukosta Y (kutsutaan yhteisdomeeniksi tai alueeksi) ja jokainen elementti verkkotunnuksesta on yhdistetty tarkalleen yhden alueen alueeseen.

Se riitti. Mutta mitä se tarkalleen tarkoittaa?

Tämä määritelmä kertoo meille, että tietokone on kone toimintojen laskemiseen.

Miksi?

Koska tietokoneet muuttavat mielivaltaisen syötteen joksikin ulostuloksi. Toisin sanoen, ne ratkaisevat ongelmia. Kaksi funktion määritelmää, yksi, jonka tunnemme hyvin, ja muodollinen, yhtyvät monissa käytännön tarkoituksissa.

Matemaattisen määritelmän avulla voimme kuitenkin päästä mielenkiintoisiin johtopäätöksiin, kuten käsittelemättömien toimintojen olemassaoloon (eli ongelmiin ilman ratkaisua):

Miksi kaikkia toimintoja ei voida kuvata algoritmeina.

Pelisäännöt

Väitteidemme helpottamiseksi kuvitellaan tietokoneita koneina, joilla on tulo, suoritetaan toimintosarja ja jonkin ajan kuluttua annetaan lähtö.

Kutsutaan syöttökoneen aakkosiksi, joka on joukko merkkijonoja jostakin äärellisestä joukosta. Esimerkiksi koneen aakkoset voivat olla binaarisia (0 ja 1) tai se voi olla ASCII-merkistö. Mikä tahansa äärellinen merkkijono on merkkijono - esimerkiksi '0110'.

Esitämme myös koneen tuloksen binäärisenä hyväksymis- ja hylkäyspäätöksi, joka toimitetaan, kun kone (toivottavasti) on suorittanut laskennan. Tämä abstraktio sopii hyvin yllä olevien funktioiden matemaattiseen määrittelyyn.

Näiden parametrien perusteella on tärkeää luonnehtia vielä yksi tyyppi: merkkijonojen kokoelma. Ehkä olemme huolissamme merkkijonoista, jotka kone hyväksyy, tai ehkä rakennamme koneita, jotka hyväksyvät merkkijonot tietyssä joukossa eivätkä toisia, tai ehkä kysymme, onko mahdollista suunnitella kone, joka hyväksyy kaikki tietyt asetettu eikä muissa.

Kaikissa näissä tapauksissa merkkijonojen joukkoa kutsutaan kieleksi - esimerkiksi joukko kaikkia binäärimerkkijonoja, jotka edustavat parillisia numeroita, tai joukko merkkijonoja, joissa on parillinen määrä merkkejä. On käynyt ilmi, että kielet, kuten numerot, voivat olla käydään kauppaa operaattoreiden kanssa kuten ketjutus, liitos, leikkaus ja vastaavat.

Tärkeä operaattori on Kleene-tähtioperaattori, jota käytetään myös säännöllisten lausekkeiden kanssa. Tätä voidaan pitää kaikkien mahdollisten kielen voimien yhdistelmänä. Esimerkiksi jos kielemme TO on merkkijonojen joukko {’01’, ’1’}, sitten jäsen TO * on merkkijono '0101111'.

Kirjanpito

Viimeinen palapelin osa ennen kuin todistetaan väitteemme siitä, että kaikki toiminnot eivät ole laskettavissa, on kirjanpidon käsite. Intuitiivisesti testimme osoittaa, että kieliä on enemmän; eli enemmän ongelmia kuin mahdollista ohjelmia niiden ratkaisemiseksi. Tämä toimii, koska kysymys siitä, kuuluuko merkkijono kielelle (Kyllä / Ei), on sinänsä ongelma.

Tarkemmin sanottuna testissämme todetaan, että mahdollisten ohjelmien joukko on äärettömän laskettavissa, kun taas aakkoset ovat kielettömiä loputtomasti.

Tässä vaiheessa saatat ajatella 'Ääretön on sinänsä melko outo idea, nyt minulla on kaksi niistä käsiteltäväksi!'

No, se ei ole niin paha. Laskennallisesti ääretön joukko voidaan luetella. On mahdollista sanoa: tämä on ensimmäinen elementti, tämä on toinen elementti ja niin edelleen, ja lopulta annetaan numero jokaiselle joukon elementille. Otetaan esimerkiksi parillisten numeroiden joukko. Voimme sanoa, että 2 on ensimmäinen, 4 toinen, 6 kolmas ja niin edelleen. Tällaiset joukot ovat laskettavissa ääretön tai laskettavissa.

Joillakin reaalilukujen kaltaisilla sarjoilla ei kuitenkaan ole väliä kuinka älykäs olet; yksinkertaisesti ei ole luetteloa. Nämä sarjat ovat lukemattomia äärettömiä tai lukematon.

Monet kirjanpito-ohjelmat

Haluamme ensin osoittaa, että tietokoneohjelmien joukko on laskettavissa. Tarkoituksemme vuoksi teemme tämän havainnoimalla, että kaikkien merkkijonojen joukko rajallisen aakkosen yli on laskettavissa. Tämä toimii, koska tietokoneohjelmat ovat rajallisia merkkijonoja.

Todiste se on suoraviivaista, emmekä käsittele yksityiskohtia tässä. Keskeistä on, että tietokoneohjelmia on yhtä monta kuin esimerkiksi luonnollisia numeroita.

Toistaa:

Kaikkien aakkosien kaikkien merkkijonojen joukko (esim. Aseta kaikki tietokoneohjelmat) on laskettavissa.

Lukemattomat monet kielet

Entä tämän johtopäätöksen kanssa, mitä tapahtuu näiden merkkijonojen osajoukoilla? Kysyttäessä toisella tavalla, entä kaikkien kielten joukko? Osoittautuu, että tämä sarja on laskematon.

Kaikkien aakkosien kaikkien kielten joukko on laskematon.

Jälleen kerran emme peitä todiste tässä.

Seuraukset

Vaikka ne eivät välttämättä ole heti ilmeisiä, lukemattomien kielten ja kaikkien tietokoneohjelmien kirjanpidon seuraukset ovat syvällisiä.

Miksi?

Oletetaan TO on ASCII-merkistö; ASCII-merkit ne ovat välttämättömiä vain tietokoneohjelman laatimiseksi. Voimme nähdä, että esimerkiksi JavaScript-ohjelmia edustavien merkkijonojen joukko on osajoukko TO * (tässä * on Kleenen tähtioperaattori). JavaScriptin valinta on mielivaltainen. Koska tämä ohjelmaryhmä on laskettavan joukon osajoukko, JavaScript-ohjelmien joukko on laskettavissa.

Tarkastellaan myös sitä kaikilla kielillä L voimme määritellä jonkin toiminnon f joka arvioi merkkijonoksi 1 x Se on sisällä L ja muuten 0. Kaikki nämä toiminnot ovat erilaisia. Koska kaikkien kielten joukon kanssa on 1: 1-vastaavuus ja koska kaikkien kielten joukko on laskematon, kaikkien näiden toimintojen joukko on laskematon.

Tässä on kohta syvällisesti:

Koska kaikkien kelvollisten ohjelmien joukko on laskettavissa, mutta toimintojen joukko ei, niin on oltava joitain toimintoja, joille emme yksinkertaisesti voi kirjoittaa ohjelmia.

Emme vieläkään tiedä miltä nämä ominaisuudet tai ongelmat näyttävät, mutta tiedämme niiden olevan. Tämä on nöyrä oivallus, koska on joitain ongelmia, joihin ei ole ratkaisua. Mielestämme tietokoneet ovat erittäin tehokkaita ja kykeneviä, mutta jotkut asiat ovat niiden ulottumattomissa.

Nyt kysymys kuuluu: 'Minkälaisia ​​nämä ongelmat ovat?' Ennen kuin jatkamme näiden ongelmien kuvaamista, meidän on ensin mallinnettava laskenta yleistetyllä tavalla.

Turing-koneet

Alan Turing kehitti yhden ensimmäisistä tietokoneen matemaattisista malleista. Tämä malli, jota kutsutaan Turingin koneeksi, on erittäin yksinkertainen laite, joka ottaa täysin huomioon käsityksemme laskettavuudesta.

Koneen tulo on nauha, jolle tulo on kirjoitettu. Luku- / kirjoituspäätä käyttämällä kone muuntaa syötteen tulostukseksi sarjana. Kussakin vaiheessa päätetään, kirjoitetaanko nauhalle ja mitä ja siirrytäänkö oikealle vai vasemmalle. Tämä päätös perustuu täsmälleen kahteen asiaan:

• Nykyinen symboli pään alla ja

• Koneen sisäinen tila, joka päivittyy myös, kun symboli kirjoitetaan

Siinä kaikki.

Universaalisuus

Vuonna 1926 Alan Turing ei vain kehittänyt Turing-konetta, vaan hänellä oli myös useita tärkeitä ajatuksia laskennan luonteesta kirjoittaessaan kuuluisan artikkelinsa 'Laskettavista numeroista'. Hän tajusi, että itse tietokoneohjelmaa voidaan pitää syötteenä tietokoneeseen. Tästä näkökulmasta hänellä oli kaunis ajatus siitä, että Turingin kone voisi simuloida tai suorittaa kyseisen syötteen.

Vaikka pidämme näitä ideoita itsestäänselvyytenä, Turingin päivinä ajatus tällaisesta universaalista koneesta oli läpimurto, joka mahdollisti Turingin kehittämään ratkaisemattomia ongelmia.

Kirkon-Turingin opinnäytetyö

Ennen kuin jatkamme, tarkastellaan tärkeää kohtaa: Tiedämme, että Turingin kone on laskennan malli, mutta onko se riittävän yleinen? Vastaamme tähän kysymykseen Kirkon-Turingin opinnäytetyö , joka tukee seuraavaa väitettä:

Kaikki laskettava on laskettavissa Turingin koneella.

Vaikka Turing kehitti Turingin koneen laskennan mallina, Alonzo Church kehitti myös lambda-laskennaksi tunnetun laskemallin. Nämä mallit ovat tehokkaita, koska ne molemmat kuvaavat tietojenkäsittelyä ja tekevät sen tavalla, joka on yhtä suuri kuin mikä tahansa nykyinen tietokone tai mikä tahansa tietokone. Tämä tarkoittaa sitä, että voimme käyttää Turingin konetta kuvaamaan etsimäsi ratkaisemattomat ongelmat tietäen, että havainnot koskevat kaikkia mahdollisia tietokoneita.

Tunnistettavuus ja päätettävyys

Meidän on peitettävä hieman enemmän taustaa, ennen kuin kuvataan konkreettisesti ratkaisematon ongelma, nimittäin kielentunnistimien käsitteet ja kielen ratkaisevat tekijät.

Kieli on tunnistettavissa, jos on olemassa Turingin kone, joka tunnistaa sen.

Y

Kieli on ratkaistavissa, jos siellä on Turingin kone.

Kielen tunnistamiseksi Turingin koneen on hyväksyttävä kaikki merkkijonot kielessä, eikä se saa hyväksyä mitään, mitä ei ole kielellä. Voit hylätä tai toistaa nämä merkkijonot. Ollakseen päätöksentekijä, Turingin koneen on aina lopetettava syöttönsä hyväksymällä tai hylkäämällä.

Tässä ajatus merkinnän lopettamisesta on kriittinen. Itse asiassa näemme, että päätöksentekotekijät ovat tehokkaampia kuin tunnistimet. Myös ongelma voidaan ratkaista, toisin sanoen, toiminto voidaan ratkaista vain, jos on olemassa Turingin kone, joka päättää funktion kuvaaman kielen.

Sallimattomuus

Jos olet koskaan kirjoittanut tietokoneohjelman, sinun on varmasti tiedettävä, miltä tuntuu istua siellä, vain katsomalla, kuinka tietokone pyörii, kun ohjelma on käynnissä. Ei tiedetä, viekö ohjelma kauan vai onko koodissa jokin virhe, joka aiheuttaa loputtoman silmukan. Olet ehkä jopa miettinyt, miksi kääntäjä ei tarkista koodia sen selvittämiseksi, pysähtyykö se vai toistuuko se ikuisesti, kun se toimii.

Kääntäjällä ei ole tällaista hallintaa, koska sitä ei vain voi tehdä. Käännösinsinöörit eivät ole tarpeeksi älykkäitä tai niiltä puuttuu resursseja, mielivaltaisen tietokoneohjelman tarkistaminen sen pysäyttämiseksi on yksinkertaisesti mahdotonta.

Voimme testata tämän Turingin koneella. Turingin koneita voidaan kuvata merkkijonoina, joten niitä on lukumäärä. Oletetaan, että M_yksi, M₂ja niin edelleen muodostavat kaikkien Turingin koneiden sarjan. Määritämme seuraavan toiminnon:

f (i, j) = 1 si M_ihyväksytj>, 0 päinvastoin

Tässä on 'M-merkkijonokoodauksen' syntaksi ja tämä funktio edustaa ongelmaa tuottaa 1, jos M_ipysähtyy hyväksyessään M_jtulona ja ulostulona 0 päinvastoin. Huomaa, että M_itäytyy pysähtyä (eli olla kaupan rikkoja). Tämä on välttämätöntä, koska haluamme kuvata ratkaisemattoman funktion (eli ongelman ilman ratkaisua).

Määritetään nyt myös kieli L joka koostuu Turingin koneiden merkkijonokoodauksista, jotka EI hyväksy omia kuvauksiaan:

L =

Esimerkiksi jotkut koneet M_yksivoi antaa 0 tuloa vartenyksi& gt, kun taas muu kone M₂voi antaa lähdön 1 tuloksi2>. Osoittaaksemme, että tämä kieli on ratkaisematon, kysymme, mitä M_L, kone, joka päättää kielen L, kun sille annetaan oma kuvausL> syötteenä. On olemassa kaksi mahdollisuutta:

M_LhyväksytL>

tai

M_LkieltääL>

Si M_Lhyväksyy oman koodauksensa, joten se tarkoittaaL> ei ole kielellä L. Kuitenkin, jos näin oli, niin M_LEn olisi pitänyt hyväksyä koodaustasi ensinnäkin. Toisaalta, jos M_Lei hyväksy omaa koodaustaanL> on kielellä L, sitten M_Lsen olisi pitänyt hyväksyä merkkijonokoodauksesi.

Molemmissa tapauksissa meillä on paradoksi tai matemaattisesti ristiriita, mikä osoittaa, että L-kieltä ei voida päättää; siksi olemme kuvanneet ensimmäisen ratkaisemattoman ongelmamme.

Ongelman lopettaminen

Vaikka juuri kuvailemamme ongelma ei ehkä vaikuta merkitykselliseltä, se voidaan supistaa muihin ratkaisemattomiin käytännön merkityksellisiin ongelmiin, erityisesti pidätysongelma :

Tyhjässä merkkijonossa pysähtyvien Turingin koneiden koodausten kieli.

Pysäytysongelma koskee kysymystä, miksi kääntäjät eivät voi havaita loputtomia solmuja aikaisin. Jos emme pysty määrittämään, päättyykö ohjelma tyhjään merkkijonoon, niin kuinka voisimme selvittää, johtaako sen toteutus ääretön solmu? Tässä vaiheessa voi tuntua heiluttamalla käsiämme yksinkertaisesta johtopäätöksestä, mutta tajusimme, ettei mikään Turingin kone osaa sanoa pysähtykö tietokoneohjelma vai pysyykö se solmuna ikuisesti. Tämä on suuri ongelma käytännön sovelluksissa, eikä sitä voida ratkaista Turingin koneella tai muulla tietokoneella. IPhone ei voi ratkaista tätä ongelmaa. Monilla ytimillä varustettu työpöytä ei voi ratkaista tätä ongelmaa. Pilvi ei pysty ratkaisemaan tätä ongelmaa. Vaikka joku haluaisi keksiä kvanttitietokoneen, hän ei silti pysty ratkaisemaan pysäytysongelmaa.

Yhteenveto

Laskettavuuden teoriaa tarkastellessamme olemme havainneet, kuinka monta toimintoa ei voida laskea missään sanan tavallisessa merkityksessä laskentaperusteen avulla. Määritämme tarkalleen, mitä tarkoitamme laskennalla, palataksemme takaisin Turingin inspiraatioon omasta kokemuksestaan ​​kynällä ja paperilla Turingin koneen virallistamiseksi. Olemme nähneet, kuinka tämä malli voi laskea kaiken, mitä mikä tahansa nykyinen tai huomisen tietokone voi laskea, ja tajusimme luokan ongelmista, joita ei voida ollenkaan laskea.

Silti laskettavuudella on haittapuoli. Se, että voimme ratkaista ongelman, ei tarkoita, että voimme ratkaista sen nopeasti. Loppujen lopuksi, mitä hyötyä tietokoneesta on, jos sen laskenta ei tule loppuun ennen kuin aurinko kääntää novan meihin kymmenien miljoonien vuosien ajan tulevaisuudessa?

Jättämällä laskettavat toiminnot ja kielet taakse, keskustelemme nyt laskennan monimutkaisuudesta, tehokkaan laskennan ja kuuluisan P vs. NP.

Monimutkaisuus

Hidas vs. Nopeasti

Tietojenkäsittelytieteen tutkijat tunnistavat monenlaisia ​​ongelmia, ja kahteen meille tärkeään luokkaan kuuluvat ongelmat, jotka tietokoneet voivat ratkaista nopeasti tai tehokkaasti, tunnetaan nimellä P ja ongelmat, joiden ratkaisut voidaan nopeasti tarkistaa, mutta joita ei saada nopeasti, tunnetaan nimellä Esimerkiksi .

Oletetaan esimerkiksi, että olet vastuussa online-treffipalvelun algoritmien kehittämisestä ja joku kysyy: 'Voivatko kaikki saada treffin?' Vastaus yhdistää yhteensopivat henkilöt niin, että kaikki sopivat yhteen. Osoittautuu, että tämän ongelman ratkaisemiseksi on olemassa tehokkaita algoritmeja. Tämä ongelma on joukossa P .

Entä jos haluaisimme tunnistaa suurimman veljeyden käyttäjien keskuudessa? Veljeskunnalla tarkoitamme suurinta verkostoa yksilöistä, jotka ovat yhteensopivia keskenään. Kun käyttäjien määrä on vähäinen, tämä ongelma voidaan ratkaista nopeasti. Voimme helposti tunnistaa esimerkiksi killan, jossa on kolme käyttäjää. Kuitenkin, kun alamme etsiä suurempia järjestöjä, ongelmaa on yhä vaikeampaa ratkaista. Tämä ongelma on joukossa Esimerkiksi .

Muodolliset määritelmät

P on joukko ongelmia, jotka voidaan ratkaista polynomiajassa. Toisin sanoen, polynomifunktio rajoittaa laskennallisten vaiheiden määrää ongelman kokoon nähden. Tiedämme, että kysymys 'Voivatko kaikki treffata?' Tunnetaan myös nimellä kahdenvälinen sattumaongelma , Se on sisällä P .

Esimerkiksi on joukko ongelmia, jotka ovat todennettavissa polynomi-ajassa. Tämä sisältää tietysti kaikki P: n ongelmat; emme kuitenkaan tiedä, onko tämä suojaus tiukka. Tiedämme ongelmista, jotka ovat tehokkaasti todennettavissa, mutta joita ei voida ratkaista tehokkaasti, mutta emme tiedä, onko ongelma todella liukenematon. Veljeysongelma on yksi niistä ongelmista. Tiedämme, että voimme varmistaa ratkaisun tehokkaasti, mutta emme tiedä varmasti, pystymmekö ratkaisemaan ongelman tehokkaasti.

Viimeisenä, NP-täydellinen on joukko ongelmia, jotka ovat kaikkein vaikeimpia ongelmia Esimerkiksi . Ne tunnetaan vaikeimpina, koska kaikki ongelmat Esimerkiksi voidaan muuntaa tehokkaasti NPC . Tämän seurauksena, jos joku löysi tehokkaan ratkaisun ongelmaan NPC , kaikenlaisia Esimerkiksi imeytyisi P . Myös veljeyden ongelma on NPC

Siksi olemme päässeet ongelman P vastaan Esimerkiksi . Monet tietojenkäsittelytieteen tutkijat ja matemaatikot uskovat siihen vahvasti P Y Esimerkiksi ne eivät ole samanlaisia. Jos ne olisivat, seuraukset olisivat perusteettomia. Suuri osa tämän päivän digitaalisesta infrastruktuurista perustuu siihen, että siellä on ongelmia Esimerkiksi joita ei ole P . Jos näin ei olisi, esimerkiksi salausmenetelmät romahtavat yhdessä yössä, jolloin henkilö, jolla on tehokas ratkaisu NPC voi kumota jopa tiukimmatkin suojausprotokollat.

Jäljitettävyyden hienovaraisuudet

Tietokoneiden aloittelijoille ero matchmaking- ja killan ongelmien välillä ei vaikuta suurelta. Itse asiassa ero ongelman välillä P ja ongelma Esimerkiksi se voi olla hyvin hienovarainen. Kyky kertoa ero on tärkeää kaikille, jotka suunnittelevat algoritmeja todellisessa maailmassa.

Harkitse lyhimmän polun ongelmaa. Kun otetaan huomioon kaksi sijaintia, tavoitteena on tunnistaa lyhin reitti niiden välillä. IPhone laskee tämän millisekunnissa. Tämä on laskennallisesti hoidettavissa oleva ongelma.

Harkitse toisaalta haukka-ongelmaa, jossa tavoitteena on käydä osassa mahdollisia määränpäätä, jotka päättyvät lähtöpaikkaan matkan aikana mahdollisimman lyhyen matkan. Tämä ongelma on samanlainen kuin lyhimmän polun ongelma, mutta on NP-täydellinen; se selittää myös, miksi toimitusketjun logistiikka on miljardin dollarin teollisuus.

Itse asiassa voimme olla vieläkin hienovaraisempia. Lyhyimmän polun (P) sijaan voimme pyytää pisintä polkua ilman solmua. On käynyt ilmi, että pisin polkuongelma on myös NP-täydellinen.

Tästä hienovaraisesta erosta on monia muita esimerkkejä, mukaan lukien kärkipisteiden tunnistaminen kahdenvälisessä vs. yleiset tai tyydyttävät Boolen kaavat, joissa on kaksi ja kolme litraalia lauseessa. Asia on, että ei ole heti selvää, onko ongelma P: ssä vai NP: ssä, joten ajonaika-analyysin syy on kriittinen taito. Jos suunniteltava algoritmi koskee P: n ongelmaa, tiedämme, että on olemassa tehokas ratkaisu. Jos ongelma on toisaalta NP: ssä, meillä on vahva tapaus vastustaa ratkaisun etsimistä, koska algoritmi yleensä yksinkertaisesti vie liian kauan ongelman ratkaiseminen.

Yhteenveto

Tässä monimutkaisuustestissä määritellään ongelmaluokat P ja NP. P edustaa epävirallisesti ongelmia, jotka tietokone voi ratkaista tehokkaasti, kun taas NP edustaa tehokkaasti todennettavissa olevia ongelmia.

Kukaan ei ole pystynyt osoittamaan, että P ei ole yhtä suuri kuin NP. Jos nämä kaksi ongelmaluokkaa ovat samanarvoisia, se tunnetaan nimellä P vs. NP ja se on nykypäivän tärkein avoin teoreettisen laskennan ongelma, ellei koko matematiikka. Itse asiassa vuonna 2000 Clay Math Institute nimitti ongelman P vs. NP yhtenä matematiikan seitsemästä tärkeimmistä avoimesta kysymyksestä ja on tarjonnut miljoonan dollarin palkkion testistä, joka määrittää ratkaisun tähän ongelmaan.

johtopäätös

Tässä artikkelissa käsittelemme laskettavuuden ja monimutkaisuuden ulottuvuuksia vastaamalla suuriin kysymyksiin, kuten 'Mikä on tietokone?' Vaikka yksityiskohdat voivat olla ylivoimaisia, on syytä muistaa useita syvällisiä oppimisia:

• On joitain asioita, joita ei yksinkertaisesti voida laskea, kuten pysäytysongelma.

• On joitain asioita, joita ei voida laskea tehokkaasti, kuten NPC: n ongelmat.

Yksityiskohtia tärkeämpiä ovat tapoja ajatella laskennasta ja laskennallisista ongelmista. Työelämässämme ja jopa jokapäiväisessä elämässämme voi törmätä ennennäkemättömiin ongelmiin ja voimme käyttää todistettuja työkaluja ja tekniikoita parhaan toimintatavan määrittämiseen.