Technológie

Úvod do teórie a zložitosti vypočítateľnosti

Zamysleli ste sa niekedy nad: Čo presne je to za zariadenie, o ktorom čítate tento článok? Čo je to počítač?

Výpočtová veda siaha do doby dávno predtým, ako si tieto moderné výpočtové zariadenia vôbec mohli predstaviť. V priemysle, kde sa často kladené otázky točia okolo programovacích jazykov, rámcov a knižníc, sme často považovali za samozrejmé základné koncepty, vďaka ktorým počítač tiká.

Ale tieto počítače, ktoré, zdá sa, majú nekonečný potenciál - majú nejaké obmedzenia? Existujú problémy, ktoré nemožno vyriešiť pomocou počítačov?

Teória a zložitosť vypočítateľnosti

V tomto článku sa budeme týmto otázkam venovať odstupom od podrobností o programovacích jazykoch a počítačových architektúrach. Pochopením sily a obmedzení počítačov a algoritmov môžeme zlepšiť naše myslenie a lepšie uvažovať o rôznych stratégiách.

Abstraktný pohľad na prácu s počítačom prináša výsledky, ktoré obstáli v skúške času a sú pre nás dnes rovnako cenné, ako keď boli pôvodne vyvinuté v 70. rokoch.

Vypočítateľnosť

Čo je to počítač? Čo je problém?

V škole nás často učia mentálny model problémov a funkcií, ktorý znie asi takto:

Funkcia je postup, ktorý použijete na vstup x, aby ste našli výstup f (x).

Ukázalo sa matematická definícia je iný:

Funkcia je množina usporiadaných párov, takže prvý prvok každého páru je zo súpravy X (nazýva sa doména), druhý prvok každého páru je zo súpravy Y (nazýva sa codomain alebo rozsah) a každý prvok z doména je spárovaná s presne jedným prvkom rozsahu.

To bolo celkom sústo. Čo to ale presne znamená?

Funkcia

Táto definícia nám hovorí, že počítač je stroj na výpočtové funkcie.

Prečo?

Pretože počítače transformujú ľubovoľný vstup na nejaký výstup. Inými slovami, riešia problémy. Dve definície funkcií, jedna, ktorú tak dobre poznáme, a formálna, sa z mnohých praktických dôvodov zhodujú.

čo z toho nie je dôvodom, prečo je zabezpečenie webových aplikácií na strane servera zložité

Matematická definícia nám však umožňuje dospieť k zaujímavým záverom, ako je napríklad existencia nepočítateľných funkcií (t. J. Neriešiteľné problémy):

Pretože nie každú funkciu možno označiť ako algoritmus.

Pravidlá hry

Aby sme pomohli argumentovať, predstavme si počítače ako stroje, ktoré prijímajú určitý vstup, vykonávajú postupnosť operácií a po určitom čase dávajú určitý výstup.

Vstup budeme nazývať abeceda stroja; teda množinu reťazcov znakov z nejakej konečnej množiny. Napríklad abeceda stroja môže byť binárna (0 s a 1 s) alebo to môže byť znaková sada ASCII. Akákoľvek konečná postupnosť znakov je reťazec - napríklad „0110“.

Ďalej budeme výstup stroja predstavovať ako binárne rozhodnutie prijať-odmietnuť, ktoré sa doručí, keď stroj (dúfajme) dokončí svoj výpočet. Táto abstrakcia dobre zapadá do matematickej definície funkcií z minulosti.

Prijať-odmietnuť počítač

Príklad overenia tvaru Angular 4

Vzhľadom na tieto parametre je dôležité charakterizovať ešte jeden typ: kolekciu reťazcov. Možno nám záleží na množine strún, ktorú prijíma nejaký stroj, alebo možno staviame stroj, ktorý prijíma struny v určitej množine a na žiadnych iných, alebo sa možno pýtame, či je vôbec možné navrhnúť stroj, ktorý v niektorých prijíma všetko. konkrétna sada a žiadne ďalšie.

Vo všetkých týchto prípadoch sa množina reťazcov nazýva jazyk - napríklad množina všetkých binárnych reťazcov, ktoré predstavujú párne čísla, alebo množina reťazcov, ktorá má párny počet znakov. Ukázalo sa, že jazyky, napríklad čísla, môžu byť operované s operátormi ako zreťazenie, spojenie, križovatka a podobne.

Jedným z dôležitých operátorov je hviezdny operátor Kleene, ktorý sa tiež používa s regulárnymi výrazmi. Dá sa to považovať za spojenie všetkých možných jazykových schopností. Napríklad ak náš jazyk TO je množina reťazcov {‘01’, ’1’}, potom jeden člen DO * je reťazec „0101111“.

Spočítateľnosť

Posledným kúskom skladačky, než dokážeme svoje tvrdenie, že nie všetky funkcie sú vypočítateľné, je koncept spočítateľnosti. Náš dôkaz intuitívne ukáže, že existuje viac jazykov; to znamená, že existuje viac problémov, ako existuje počet možných programov na ich riešenie. Funguje to preto, lebo otázka, či reťazec patrí do jazyka (Áno / Nie), je sama o sebe problémom.

Presnejšie, náš dôkaz tvrdí, že množina možných programov je nespočetne nekonečná, zatiaľ čo množina jazykov nad abecedou je nespočetne nekonečná.

V tejto chvíli si možno myslíte: „Nekonečno je dosť zvláštny nápad sám o sebe; teraz sa musím vysporiadať s dvoma z nich! “

Nie je to také zlé. Počítateľne nekonečná množina je taká, ktorú je možné vymenovať. Je možné povedať, že ide o prvý prvok, ide o druhý prvok atď., Prípadne každému prvku množiny priradíte číslo. Vezmime si napríklad množinu párnych čísel. Môžeme povedať, že 2 sú prvé, 4 druhé, 6 tretie atď. Takéto množiny sú spočítateľne nekonečné alebo spočítateľné.

Pri niektorých množinách však, rovnako ako skutočné čísla, nezáleží na tom, aký ste šikovný; proste neexistuje nijaký výčet. Tieto súpravy sú nespočetne nekonečný alebo nespočetné.

Nespočetne veľa programov

Najprv chceme ukázať, že množina počítačových programov je spočítateľná. Pre naše účely to robíme pozorovaním, že množina všetkých reťazcov nad konečnou abecedou je spočítateľná. To funguje, pretože počítačové programy sú samy konečnými reťazcami.

Dôkaz je priamy a nezaoberáme sa tu podrobnosťami. Kľúčovou vecou je, že existuje toľko počítačových programov, koľko je, povedzme, prirodzených čísel.

Zopakovať:

Sada všetkých reťazcov ľubovoľnej abecedy (napr. Sada všetkých počítačových programov) je spočítateľná.

Nespočetne veľa jazykov

Vzhľadom na tento záver, čo s podmnožinami týchto reťazcov? Na inú otázku, čo so súborom všetkých jazykov? Ukazuje sa, že táto sada je nespočetná.

Množina všetkých jazykov v ľubovoľnej abecede je nespočetná.

Ešte raz to neprekrývame dôkaz tu.

Dôsledky

Aj keď to nemusí byť hneď zrejmé, dôsledky spočítania jazykov a počítateľnosti súboru všetkých počítačových programov sú závažné.

Prečo?

Predpokladajme TO je sada znakov ASCII; ASCII znaky sú len tie, ktoré sú potrebné na zostavenie počítačového programu. Vidíme, že množina reťazcov, ktorá predstavuje napríklad programy JavaScriptu, je jej podmnožinou DO * (tu, * je hviezdny operátor Kleene). Výber JavaScriptu je ľubovoľný. Pretože táto sada programov je podmnožinou spočítateľnej množiny, máme k dispozícii množinu programov JavaScript.

Zvážme to navyše pre akýkoľvek jazyk Ľ , môžeme definovať nejakú funkciu f ktorý vyhodnotí na 1 ak nejaký reťazec X je v Ľ a 0 inak. Všetky tieto funkcie sú odlišné. Pretože existuje korešpondencia 1: 1 s množinou všetkých jazykov a pretože množina všetkých jazykov je nespočetná, máme množinu všetkých týchto funkcií nepočítateľnú.

Tu je hlboký bod:

Pretože množina všetkých platných programov je spočítateľná, ale množina funkcií nie, musí existovať niekoľko funkcií, pre ktoré programy jednoducho nemôžeme napísať.
rozdiel v s korporácie a c korporácie

Zatiaľ nevieme, ako tieto funkcie alebo problémy vyzerajú, ale vieme, že existujú. Toto je ponižujúce uvedomenie si, pretože existujú problémy, pre ktoré neexistuje riešenie. Počítače považujeme za mimoriadne výkonné a schopné, napriek tomu sú niektoré veci mimo ich dosah.

Teraz sa ponúka otázka: „Ako tieto problémy vyzerajú?“ Predtým, ako budeme pokračovať v popise takýchto problémov, musíme najskôr modelovať výpočet zovšeobecneným spôsobom.

Turingove stroje

Jeden z vôbec prvých matematických modelov počítača vyvinul Alan Turing. Tento model s názvom Turingov stroj je mimoriadne jednoduché zariadenie, ktoré úplne vystihuje našu predstavu o vypočítateľnosti.

Turingov stroj

Vstupom do zariadenia je páska, na ktorú bol vstup napísaný. Pomocou čítacej / zapisovacej hlavy stroj premieňa vstup na výstup pomocou série krokov. V každom kroku sa rozhoduje o tom, či a čo na pásku napísať a či ju posunúť doprava alebo doľava. Toto rozhodnutie je založené na presne dvoch veciach:

Aktuálny symbol pod hlavou a
Interný stav stroja, ktorý sa tiež aktualizuje pri zapisovaní symbolu

To je všetko.

Univerzálnosť

V roku 1926 Alan Turing nielen vyvinul Turingov stroj, ale mal aj niekoľko ďalších dôležitých poznatkov o povahe výpočtu, keď napísal svoj slávny príspevok „O vypočítateľných číslach“. Uvedomil si, že samotný počítačový program možno považovať za vstup do počítača. Z tohto pohľadu mal krásnu predstavu, že Turingov stroj dokáže tento vstup simulovať alebo vykonať.

Aj keď tieto nápady dnes považujeme za samozrejmé, v časoch Turingovho dňa bola predstava takého univerzálneho stroja hlavným prielomom, ktorý umožnil Turingovi vyvinúť neriešiteľné problémy.

Cirkevná turingova téza

Skôr ako pokračujeme, preskúmajme dôležitý bod: Vieme, že Turingov stroj je model výpočtu, ale je to dosť všeobecné? Aby sme odpovedali na túto otázku, obrátime sa na Cirkevná turingova téza , ktorý dáva dôveryhodnosť tomuto vyhláseniu:

Všetko vypočítateľné je vypočítateľné pomocou Turingovho stroja.

Zatiaľ čo Turing vyvinul Turingov stroj ako model výpočtu, Alonzo Church vyvinul aj model výpočtu známy ako lambda-kalkul. Tieto modely sú výkonné, pretože opisujú výpočet, a to rovnakým spôsobom ako ktorýkoľvek z dnešných počítačov, alebo vlastne akýkoľvek počítač. To znamená, že môžeme pomocou Turingovho stroja opísať neriešiteľné problémy, ktoré hľadáme, s vedomím, že naše zistenia sa budú týkať všetkých možných počítačov v minulosti, súčasnosti i mimo nich.

Rozpoznateľnosť a rozhodovateľnosť

Pred konkrétnym popisom neriešiteľného problému, konkrétne pojmov rozpoznávače jazykov a rozhodovacích jazykov, musíme pokryť ešte trochu viac pozadia.

Jazyk je rozpoznateľný, ak existuje Turingov prístroj, ktorý ho rozpozná.

a

Jazyk je určiteľný, ak existuje Turingov stroj, ktorý o ňom rozhoduje.

Aby Turingov stroj rozpoznal jazyk, musí prijať každý reťazec v jazyku a nesmie akceptovať nič, čo nie je v tomto jazyku. Môže to odmietnuť alebo vytvoriť slučku na takomto reťazci. Aby mohol byť Turingov stroj rozhodujúcim činiteľom, musí sa vždy zastaviť na svojom vstupe buď prijatím, alebo odmietnutím.

Tu je myšlienka zastavenia na vstupe kritická. V skutočnosti vidíme, že rozhodovatelia sú mocnejší ako rozpoznávatelia. Okrem toho je problém riešiteľný, alebo inak povedané, funkcia je určiteľná, iba ak existuje Turingov stroj, ktorý rozhoduje o jazyku opísanom funkciou.

Nerozhodnuteľnosť

Ak ste niekedy písali počítačový program, určite musíte poznať ten pocit, keď tam sedíte a len sledujete, ako počítač po spustení programu roztáča kolesá. Neviete, či program trvá len dlho alebo či je v kóde nejaká chyba spôsobujúca nekonečnú slučku. Možno ste sa už pýtali, prečo kompilátor nekontroluje kód, aby zistil, či sa pri spustení zastaví alebo navždy opakuje.

Kompilátor takúto kontrolu nemá, pretože sa to jednoducho nedá urobiť. Nie je to tak, že inžinieri prekladačov nie sú dosť inteligentní alebo nemajú zdroje; je jednoducho nemožné skontrolovať ľubovoľný počítačový program a zistiť, či sa zastaví.

Môžeme to dokázať pomocou stroja Turing. Turingove stroje možno označiť ako struny, takže ich je nespočetné množstvo. Predpokladajme, že M_jeden, M.₂, a tak ďalej, tvoria sadu všetkých Turingových strojov. Definujme nasledujúcu funkciu:

f (i, j) = 1, ak M_iprijímaj>, 0 inak

Tu je syntax pre „kódovanie reťazcov M“ a táto funkcia predstavuje problém výstupu 1, ak M_izastaví prijatím M_jako vstup a výstup 0 inak. Všimnite si, že M_isa musí zastaviť (t. j. byť rozhodujúcim). Toto je potrebné, pretože chceme popísať nerozhodnutú funkciu (t. J. Neriešiteľný problém).

Definujme teraz jazyk Ľ ktorý pozostáva z kódovania reťazcov Turingových strojov, ktoré Neakceptujú svoje vlastné popisy:

L = M neprijíma

Napríklad nejaký stroj M_jedenmôže na výstupe vydať 0jeden> zatiaľ čo iný stroj M₂môže na výstupe 12>. Aby sme dokázali, že tento jazyk je nerozhodný, pýtame sa, čo M_Ľ, stroj, ktorý rozhoduje o jazyku L, robí, keď má vlastný popisĽ> ako vstup. Existujú dve možnosti:

M_ĽprijímaĽ>

alebo

M_ĽodmietaĽ>

Ak M_Ľakceptuje svoje vlastné kódovanie, to potom znamenáĽ> nie je v jazyku L; ak by to však bolo tak, potom M_Ľna prvom mieste nemal prijať jeho kódovanie. Na druhej strane, ak M_Ľneakceptuje vlastné kódovanieĽ> je v jazyku L, takže M_Ľmal prijať jeho kódovanie reťazca.

V obidvoch prípadoch máme paradox alebo matematicky vyjadrený rozpor, ktorý dokazuje, že jazyk L je nerozhodnuteľný; teda sme opísali náš prvý neriešiteľný problém.

Problém zastavenia

Aj keď sa problém, ktorý sme práve opísali, nemusí javiť ako relevantný, je možné ho znížiť na ďalšie neriešiteľné problémy praktického významu, predovšetkým na zastavenie problému :

Jazyk kódovania Turingových strojov, ktorý sa zastaví na prázdnom reťazci.

Problém zastavenia sa týka otázky, prečo prekladače nedokážu detekovať nekonečné slučky skôr. Ak nemôžeme určiť, či sa program končí na prázdnom reťazci, ako by sme mohli zistiť, či by jeho vykonanie malo za následok nekonečnú slučku?

V tomto okamihu by sa mohlo zdať, že sme len mávali rukami, aby sme dosiahli nejaký jednoduchý záver; v skutočnosti sme si však uvedomili, že žiadny Turingov stroj nedokáže určiť, či sa počítačový program zastaví alebo zostane v slučke navždy. Toto je dôležitý problém s praktickými aplikáciami a nedá sa vyriešiť na Turingovom stroji alebo na akomkoľvek inom počítači. IPhone nemôže tento problém vyriešiť. Desktop s mnohými jadrami nemôže tento problém vyriešiť. Cloud tento problém nedokáže vyriešiť. Aj keby niekto vynašiel kvantový počítač, stále by nebol schopný vyriešiť problém zastavenia.

Zhrnutie

Pri našom skúmaní teórie vypočítateľnosti sme videli, ako existuje veľa funkcií, ktoré nie je možné vypočítať v bežnom zmysle slova počítacím argumentom. Presne sme definovali, čo máme na mysli výpočtom, a to až k Turingovej inšpirácii z jeho vlastných skúseností s perom a papierom, aby sme formovali Turingov stroj. Videli sme, ako tento model dokáže vypočítať čokoľvek, čo ktorýkoľvek počítač dnes alebo pre zajtra predpokladáme, a uvedomili sme si triedu problémov, ktoré nie sú vôbec vypočítateľné.

Vypočítateľnosť má napriek tomu nevýhodu. To, že môžeme vyriešiť problém, neznamená, že ho môžeme vyriešiť rýchlo. Nakoniec, aký dobrý je počítač, ak sa jeho výpočet neskončí skôr, ako na nás slnko vyjde nova desiatky miliónov rokov v budúcnosti?

Ak necháme za sebou výpočtové funkcie a jazyky, teraz diskutujeme o zložitosti výpočtu, zisťovaní efektívnych výpočtov a známom probléme P vs. NP.

Zložitosť

Pomaly vs. rýchlo

Počítačoví vedci uznávajú rôzne triedy problémov a dve triedy, na ktorých nám záleží, zahŕňajú problémy, ktoré môžu počítače vyriešiť rýchlo alebo efektívne, známe ako P a problémy, ktorých riešenia možno rýchlo overiť, ale nemožno ich rýchlo získať, známe ako Napríklad .

gestalt teória zrakového vnímania

Predpokladajme napríklad, že ste zodpovední za vývoj algoritmov pre službu online zoznamiek a niekto si položí otázku: „Môže každý dostať rande?“ Odpoveď sa ponúka na spárovaní kompatibilných jednotlivcov, aby boli spárovaní všetci. Ukázalo sa, že existujú efektívne algoritmy na riešenie tohto problému. Tento problém je v množine P .

Čo by sa stalo, keby sme chceli určiť najväčšiu kliku medzi našimi používateľmi? Pod klikou rozumieme najväčšiu sieť jednotlivcov, ktoré sú navzájom kompatibilné. Ak je počet používateľov nízky, tento problém je možné rýchlo vyriešiť. Ľahko identifikujeme povedzme kliku s 3 používateľmi. Keď začneme hľadať väčšie kliky, problém je čoraz ťažšie vyriešiť. Tento problém je v množine Napríklad .

Formálne definície

P je množina problémov, ktoré sú riešiteľné v polynomiálnom čase. To znamená, že počet výpočtových krokov je ohraničený polynomickou funkciou vzhľadom na veľkosť problému. Vieme, že „Môže každý mať rande?“ otázka, známa tiež ako problém dvojstrannej zhody , je v P .

Napríklad je množina problémov, ktoré sa dajú overiť v polynomiálnom čase. To samozrejme zahŕňa všetky problémy v P; nevieme však, či je toto obmedzenie prísne. Vieme o problémoch, ktoré je možné efektívne overiť, ale nie je ich efektívne vyriešiť, ale nevieme, či je problém skutočne neriešiteľný. Jedným z takýchto problémov je problém s klikou. Vieme, že môžeme efektívne overiť riešenie, ale nevieme s istotou, či môžeme problém vyriešiť efektívne.

Nakoniec NP-úplné je súbor problémov, ktoré sú najťažšími problémami Napríklad . Oni sú označovaní ako najťažšie, pretože akýkoľvek problém v Napríklad sa dá efektívne premeniť na NPC . Výsledkom by bolo, keby niekto v roku 2006 identifikoval efektívne riešenie problému NPC , potom celá trieda Napríklad by bol absorbovaný P . Problém s klikami je tiež v NPC .

P vs. NP

Takto prichádzame k problému P vs. Napríklad . Mnoho počítačových vedcov a matematikov tomu pevne verí P a Napríklad nie sú si rovní. Keby boli, dôsledky by boli viac ako hlboké. Väčšina dnešnej digitálnej infraštruktúry sa spolieha na to, že sú v nej problémy Napríklad ktoré nie sú v P . Ak by to tak nebolo, potom by sa napríklad kryptografické metódy cez noc zrútili, čo by osobe disponujúcej efektívnym riešením umožnilo NPC problém podkopať aj tie najprísnejšie bezpečnostné protokoly.

Jemnosť príťažlivosti

Pre začínajúcich informatikov by sa rozdiel medzi problémami priraďovania a kliky nemusel javiť ako veľký problém. V skutočnosti je rozdiel medzi problémom v P a problém v Napríklad môže byť veľmi jemný. Schopnosť rozpoznať rozdiel je dôležitá pre každého, kto navrhuje algoritmy v reálnom svete.

Zvážte problém s najkratšou cestou. Vzhľadom na dve polohy je cieľom určiť najkratšiu cestu medzi nimi. IPhone to počíta v priebehu niekoľkých milisekúnd. Toto je výpočtovo príťažlivý problém.

Na druhej strane zvážte problém obchodného cestujúceho, kde je cieľom navštíviť podskupinu možných cieľov končiacich pri počiatku pri prekonávaní čo najkratšej vzdialenosti. Tento problém je podobný problému s najkratšou cestou, ale je NP-úplný; tiež to vysvetľuje, prečo je logistika dodávateľského reťazca odvetvím s miliardami dolárov.

node js robí asynchrónne volanie synchrónne

V skutočnosti môžeme byť ešte jemnejší. Namiesto toho, aby sme požiadali o najkratšiu cestu (P), môžeme požiadať o najdlhšiu cestu bez cyklov. Ukázalo sa, že problém s najdlhšou cestou je tiež NP-úplný.

Existuje mnoho ďalších príkladov tohto jemného rozlíšenia, vrátane identifikácie vrcholových obalov v bipartitných vs. všeobecných grafoch alebo uspokojenia boolovských vzorcov s dvoma vs. tromi literálmi na klauzulu. Jedná sa o to, že nie je okamžite zrejmé, či je problém v P alebo NP, a preto je analýza prevádzkového času kritickou zručnosťou. Ak je algoritmus, ktorý musí byť navrhnutý, určený pre problém v P, potom vieme, že existuje efektívne riešenie. Ak je problém na druhej strane v NP, potom musíme argumentovať proti hľadaniu riešenia, pretože riešenie algoritmu by všeobecne trvalo jednoducho príliš dlho.

Zhrnutie

Pri tomto skúmaní zložitosti sme definovali triedy úloh P a NP. P neformálne predstavuje problémy, ktoré je možné efektívne vyriešiť počítačom, zatiaľ čo NP predstavuje tie, ktoré je možné efektívne overiť.

Nikto nedokázal dokázať, že P sa nerovná NP. To, či sú tieto dve triedy problémov rovnocenné, je známe ako problém P vs. NP a je to dnes najdôležitejší otvorený problém v teoretickej informatike, ak nie v celej matematike. V skutočnosti Clay Math Institute v roku 2000 označil problém P vs. NP za jednu zo siedmich najdôležitejších otvorených otázok v matematike a ponúkol odmenu v hodnote miliónov dolárov za dôkaz, ktorý určuje riešenie tohto problému.

Záver

V tomto článku sme sa ponorili do oblastí vypočítateľnosti a zložitosti a odpovedali na veľké otázky, ako napríklad: „Čo je to počítač?“ Aj keď podrobnosti môžu byť zdrvujúce, je treba pamätať na niekoľko dôležitých vecí:

Existuje niekoľko vecí, ktoré sa jednoducho nedajú vypočítať, napríklad problém so zastavením.
Existuje niekoľko vecí, ktoré sa nedajú vypočítať efektívne, napríklad problémy v NPC.

Dôležitejšie ako podrobnosti sú spôsoby uvažovania o výpočte a výpočtových problémoch. V našom profesionálnom živote a dokonca aj v každodennom živote sa môžeme stretnúť s problémami, ktoré sme nikdy predtým nevideli, a na určenie najlepšieho postupu môžeme použiť osvedčené nástroje a techniky.

Pochopenie základov

Existujú výpočtové problémy bez riešenia?

Pretože množina všetkých platných programov je spočítateľná, ale množina funkcií nie, musí existovať niekoľko funkcií, pre ktoré programy jednoducho nemôžeme napísať.