Wprowadzenie do teorii obliczalności i złożoności

Czy zastanawiałeś się kiedyś: na jakim dokładnie urządzeniu czytasz ten artykuł? Czym jest komputer?

Nauki komputerowe sięgają czasów na długo przed wyobrażeniem tych nowoczesnych urządzeń komputerowych. W branży, w której najczęściej zadawane pytania dotyczą języków programowania, frameworków i bibliotek, często braliśmy za pewnik podstawowe koncepcje, które sprawiają, że komputer działa.

Ale te komputery, które wydają się mieć nieskończony potencjał — czy mają jakieś ograniczenia? Czy są problemy, których nie można rozwiązać za pomocą komputerów?

W tym artykule odpowiemy na te pytania, odchodząc od szczegółów języków programowania i architektur komputerowych. Rozumiejąc moc i ograniczenia komputerów i algorytmów, możemy poprawić sposób myślenia i lepiej uzasadniać różne strategie.

Abstrakcyjny pogląd na przetwarzanie danych daje wyniki, które przetrwały próbę czasu, będąc dzisiaj dla nas tak samo wartościowe, jak początkowo opracowane w latach siedemdziesiątych.

Obliczalność

Czym jest komputer? Jaki jest problem?

W szkole często uczymy się mentalnego modelu problemów i funkcji, który wygląda mniej więcej tak:

Funkcja to procedura, którą stosujesz do wejścia x w celu znalezienia wyjścia f(x).

Okazuje się, że definicja matematyczna jest inna:

Funkcja jest zbiorem uporządkowanych par w taki sposób, że pierwszy element każdej pary pochodzi ze zbioru X (nazywanego dziedziną), drugi element każdej pary pochodzi ze zbioru Y (nazywanego kodziedziną lub zakresem), a każdy element domena jest sparowana z dokładnie jednym elementem zakresu.

To był niezły kęs. Ale co to dokładnie oznacza?

Ta definicja mówi nam, że komputer jest maszyną do obliczania funkcji.

Czemu?

Ponieważ komputery przekształcają dowolne dane wejściowe w pewne dane wyjściowe. Innymi słowy, rozwiązują problemy. Dwie definicje funkcji, ta, którą znamy i formalna, pokrywają się z wielu praktycznych celów.

Jednak definicja matematyczna pozwala na wyciągnięcie ciekawych wniosków, takich jak istnienie funkcji nieobliczalnych (tj. problemów nierozwiązywalnych):

Ponieważ nie każdą funkcję można opisać jako algorytm.

Zasady gry

Aby ułatwić sobie argumentację, wyobraźmy sobie komputery jako maszyny pobierające dane wejściowe, wykonujące sekwencję operacji, a po pewnym czasie dające pewne dane wyjściowe.

Wejście nazwiemy alfabetem maszyny; czyli zbiór ciągów znaków z jakiegoś skończonego zbioru. Na przykład alfabet maszyny może być binarny (0s i 1s) lub może to być zestaw znaków ASCII. Każda skończona sekwencja znaków jest ciągiem — na przykład „0110”.

Co więcej, przedstawimy dane wyjściowe maszyny jako binarną decyzję akceptuj-odrzuć, dostarczaną, gdy maszyna (miejmy nadzieję) zakończy obliczenia. Ta abstrakcja dobrze pasuje do wcześniejszej matematycznej definicji funkcji.

Biorąc pod uwagę te parametry, ważne jest, aby scharakteryzować jeszcze jeden typ: zbiór ciągów. Może zależy nam na zbiorze ciągów, który akceptuje jakaś maszyna, a może budujemy maszynę, która akceptuje ciągi w określonym zbiorze, a nie w innych, a może pytamy, czy jest w ogóle możliwe zaprojektowanie maszyny, która akceptuje wszystko w jakimś konkretny zestaw i żadnych innych.

We wszystkich tych przypadkach zestaw ciągów jest nazywany językiem — na przykład zestaw wszystkich ciągów binarnych reprezentujących liczby parzyste lub zestaw ciągów, które mają parzystą liczbę znaków. Okazuje się, że na językach, takich jak liczby, można operować operatorami, takimi jak konkatenacja, suma, przecięcie i tym podobne.

Jednym z ważnych operatorów jest operator gwiazdy Kleene, który jest również używany z wyrażeniami regularnymi. Można to traktować jako połączenie wszystkich możliwych sił języka. Na przykład, jeśli nasz język A jest zbiorem ciągów { '01', '1' }, to jednym elementem A* jest ciąg '0101111'.

Policzalność

Ostatnim elementem układanki, zanim udowodnimy nasze twierdzenie, że nie wszystkie funkcje są obliczalne, jest pojęcie policzalności. Intuicyjnie nasz dowód wykaże, że języków jest więcej; to znaczy więcej problemów niż jest możliwych programów do ich rozwiązania. Działa to, ponieważ pytanie, czy ciąg należy do języka (Tak/Nie) samo w sobie jest problemem.

Dokładniej, nasz dowód twierdzi, że zbiór możliwych programów jest przeliczalnie nieskończony, podczas gdy zbiór języków nad alfabetem jest nieprzeliczalnie nieskończony.

W tym momencie możesz pomyśleć: „Nieskończoność sama w sobie jest dość dziwną ideą; teraz mam do czynienia z dwoma z nich!”

Cóż, nie jest tak źle. Zbiór przeliczalnie nieskończony to taki, który można wyliczyć. Można powiedzieć, że to jest pierwszy element, to jest drugi element i tak dalej, ostatecznie przypisując numer do każdego elementu zestawu. Weźmy na przykład zestaw liczb parzystych. Możemy powiedzieć, że 2 to pierwsza, 4 druga, 6 trzecia i tak dalej. Takie zbiory są przeliczalnie nieskończone lub przeliczalne.

Jednak w przypadku niektórych zestawów, takich jak liczby rzeczywiste, nie ma znaczenia, jak sprytny jesteś; po prostu nie ma wyliczenia. Te zbiory są niepoliczalnie nieskończone lub niepoliczalne.

Policzalnie wiele programów

Najpierw chcemy pokazać, że zbiór programów komputerowych jest policzalny. Dla naszych celów robimy to, obserwując, że zbiór wszystkich ciągów w skończonym alfabecie jest policzalny. Działa to, ponieważ programy komputerowe same w sobie są skończonymi ciągami.

Dowód jest prosty i nie omawiamy tutaj szczegółów. Kluczowym wnioskiem jest to, że istnieje tyle programów komputerowych, ile jest, powiedzmy, liczb naturalnych.

Powtarzać:

Zbiór wszystkich ciągów znaków w dowolnym alfabecie (np. zbiór wszystkich programów komputerowych) jest policzalny.

Nieskończenie wiele języków

Biorąc pod uwagę ten wniosek, co z podzbiorami tych ciągów? Zapytany w inny sposób, co z zestawem wszystkich języków? Okazuje się, że ten zestaw jest niepoliczalny.

Zestaw wszystkich języków w dowolnym alfabecie jest niepoliczalny.

Po raz kolejny nie omawiamy tutaj dowodu.

Konsekwencje

Chociaż mogą nie być od razu widoczne, konsekwencje niepoliczalności języków i policzalności zbioru wszystkich programów komputerowych są głębokie.

Czemu?

Załóżmy, że A jest zbiorem znaków ASCII; Znaki ASCII to tylko te, które są potrzebne do skomponowania programu komputerowego. Widzimy, że zbiór łańcuchów, które reprezentują, powiedzmy, programy JavaScript, jest podzbiorem A* (tutaj * jest operatorem gwiazdy Kleene). Wybór JavaScript jest arbitralny. Ponieważ ten zbiór programów jest podzbiorem zbioru policzalnego, mamy, że zbiór programów JavaScript jest policzalny.

Dodatkowo rozważmy, że dla dowolnego języka L możemy zdefiniować funkcję f , która daje 1, jeśli jakiś ciąg x jest w L , a 0 w przeciwnym razie. Wszystkie takie funkcje są odrębne. Ponieważ istnieje korespondencja 1:1 ze zbiorem wszystkich języków i ponieważ zbiór wszystkich języków jest niepoliczalny, mamy, że zbiór wszystkich takich funkcji jest niepoliczalny.

Oto najgłębszy punkt:

Ponieważ zbiór wszystkich poprawnych programów jest policzalny, ale zbiór funkcji nie, to muszą istnieć funkcje, dla których po prostu nie możemy napisać programów.

Nie wiemy jeszcze, jak wyglądają te funkcje lub problemy, ale wiemy, że istnieją. To upokarzająca realizacja, ponieważ istnieją pewne problemy, na które nie ma rozwiązania. Uważamy, że komputery są niezwykle potężne i zdolne, ale niektóre rzeczy są poza ich zasięgiem.

Teraz pojawia się pytanie: „Jak wyglądają te problemy?” Zanim przejdziemy dalej do opisywania takich problemów, musimy najpierw uogólnić obliczenia modelowe.

Maszyny Turinga

Jeden z pierwszych matematycznych modeli komputera został opracowany przez Alana Turinga. Model ten, zwany maszyną Turinga, jest niezwykle prostym urządzeniem, które całkowicie oddaje nasze pojęcie obliczalności.

Dane wejściowe do urządzenia to taśma, na której dane wejściowe zostały zapisane. Używając głowicy odczytująco-zapisującej, maszyna zamienia dane wejściowe w dane wyjściowe poprzez szereg kroków. Na każdym kroku podejmowana jest decyzja, czy i co napisać na taśmę i czy przesunąć ją w prawo czy w lewo. Ta decyzja opiera się dokładnie na dwóch rzeczach:

• Aktualny symbol pod głową i

• Stan wewnętrzny maszyny, który jest również aktualizowany w miarę zapisywania symbolu

Otóż ​​to.

Uniwersalność

W 1926 roku Alan Turing nie tylko opracował maszynę Turinga, ale także miał wiele innych ważnych spostrzeżeń na temat natury obliczeń, kiedy napisał swoją słynną pracę „O liczbach obliczalnych”. Zdał sobie sprawę, że sam program komputerowy można uznać za dane wejściowe do komputera. Z tego punktu widzenia wpadł na piękny pomysł, że maszyna Turinga może symulować lub wykonywać te dane wejściowe.

Chociaż dziś uważamy te pomysły za oczywiste, w czasach Turinga idea tak uniwersalnej maszyny była głównym przełomem, który pozwolił Turingowi rozwinąć nierozwiązywalne problemy.

Teza Kościoła Turinga

Zanim przejdziemy dalej, przyjrzyjmy się ważnej kwestii: wiemy, że maszyna Turinga jest modelem obliczeń, ale czy jest wystarczająco ogólna? Aby odpowiedzieć na to pytanie, zwracamy się do Tezy Church-Turinga, która uwiarygadnia następujące stwierdzenie:

Wszystko, co jest obliczalne, jest obliczalne przez maszynę Turinga.

Podczas gdy Turing opracował maszynę Turinga jako model obliczeń, Alonzo Church opracował również model obliczeń znany jako rachunek lambda. Modele te są potężne, ponieważ oba opisują obliczenia i robią to w sposób podobny do każdego z dzisiejszych komputerów lub, jeśli o to chodzi, każdego komputera w historii. Oznacza to, że możemy użyć maszyny Turinga do opisania nierozwiązywalnych problemów, których szukamy, wiedząc, że nasze odkrycia będą miały zastosowanie do wszystkich możliwych komputerów w przeszłości, teraźniejszości i poza nią.

Rozpoznawalność i rozstrzyganie

Musimy omówić nieco więcej tła, zanim konkretnie opiszemy nierozwiązywalny problem, a mianowicie koncepcje aparatów rozpoznawania języka i decydentów językowych.

Język jest rozpoznawalny, jeśli istnieje maszyna Turinga, która go rozpoznaje.

oraz

Język jest rozstrzygalny, jeśli decyduje o nim maszyna Turinga.

Aby rozpoznać język, maszyna Turinga musi akceptować każdy ciąg znaków w języku i nie może akceptować niczego, co nie jest w języku. Może odrzucić lub zapętlić takie ciągi. Aby decydować, maszyna Turinga musi zawsze zatrzymać się na swoim wejściu, akceptując lub odrzucając.

W tym przypadku pomysł zatrzymania na wejściu jest krytyczny. W rzeczywistości widzimy, że osoby decydujące mają większą moc niż osoby rozpoznające. Co więcej, problem jest rozwiązywalny lub mówiąc inaczej, funkcja jest rozstrzygalna tylko wtedy, gdy istnieje maszyna Turinga, która decyduje o języku opisanym przez funkcję.

Nierozstrzygalność

Jeśli kiedykolwiek pisałeś program komputerowy, z pewnością znasz uczucie siedzenia i patrzenia, jak komputer kręci się, gdy program jest wykonywany. Nie wiesz, czy program po prostu zajmuje dużo czasu, czy jest jakiś błąd w kodzie powodujący nieskończoną pętlę. Być może nawet zastanawiałeś się, dlaczego kompilator nie sprawdza kodu, aby zobaczyć, czy zatrzyma się lub zapętli na zawsze po uruchomieniu.

Kompilator nie ma takiej kontroli, bo po prostu nie da się tego zrobić. Nie chodzi o to, że inżynierowie kompilatorów nie są wystarczająco sprytni lub brakuje im zasobów; po prostu niemożliwe jest sprawdzenie dowolnego programu komputerowego w celu ustalenia, czy się zatrzyma.

Możemy to udowodnić za pomocą maszyny Turinga. Maszyny Turinga można opisać jako struny, więc jest ich policzalna liczba. Załóżmy, że M ₁ , M ₂ itd. tworzą zbiór wszystkich maszyn Turinga. Zdefiniujmy następującą funkcję:

Tutaj <M> jest składnią „kodowania łańcuchowego M”, a ta funkcja reprezentuje problem wyprowadzenia 1, jeśli M _i zatrzyma się, przyjmując M _j jako wejście i wyprowadzenie 0 w przeciwnym razie. Zauważ, że M _i musi się zatrzymać (tj. podjąć decyzję). Jest to wymagane, ponieważ chcemy opisać funkcję nierozstrzygalną (tj. problem nierozwiązywalny).

Teraz zdefiniujmy również język L , który składa się z kodowań ciągów maszyn Turinga, które NIE akceptują własnych opisów:

Na przykład, pewna maszyna M ₁ może wyprowadzić 0 na wejście <M ₁ >, podczas gdy inna maszyna M ₂ może wyprowadzić 1 na wejście <M ₂ >. Aby udowodnić, że ten język jest nierozstrzygalny, pytamy, co robi M _L , maszyna decydująca o języku _L , kiedy otrzymuje jako dane wejściowe swój własny opis <ML >. Istnieją dwie możliwości:

M _L akceptuje <M _L >

lub

M _L odrzuca <M _L >

Jeśli M _L akceptuje własne kodowanie, oznacza to, że <M _L > nie jest w języku L; gdyby jednak tak było, to _ML nie powinien był w pierwszej kolejności akceptować swojego kodowania. Z drugiej strony, jeśli ML nie akceptuje własnego kodowania, to < _ML > jest w języku _L , więc _ML powinien zaakceptować swoje kodowanie łańcuchowe.

W obu przypadkach mamy do czynienia z paradoksem, czyli w kategoriach matematycznych sprzecznością, dowodzącą, że język L jest nierozstrzygalny; w ten sposób opisaliśmy nasz pierwszy nierozwiązywalny problem.

Zatrzymanie problemu

Chociaż problem, który właśnie opisaliśmy, może wydawać się nieistotny, można go sprowadzić do dodatkowych nierozwiązywalnych problemów o znaczeniu praktycznym, w szczególności problemu zatrzymania:

Język kodowania maszyn Turinga, które zatrzymują się na pustym ciągu.

Problem zatrzymania dotyczy pytania, dlaczego kompilatory nie mogą wykryć nieskończonych pętli z wcześniejszych wersji. Jeśli nie możemy określić, czy program kończy się na pustym łańcuchu, to jak możemy ewentualnie określić, czy jego wykonanie spowoduje nieskończoną pętlę?

W tym momencie może się wydawać, że po prostu machamy rękami, aby dojść do prostego wniosku; jednak w rzeczywistości zdaliśmy sobie sprawę, że żadna maszyna Turinga nie jest w stanie stwierdzić, czy program komputerowy zatrzyma się, czy pozostanie w pętli na zawsze. Jest to ważny problem w praktycznych zastosowaniach i nie można go rozwiązać na maszynie Turinga ani na żadnym innym komputerze. iPhone nie może rozwiązać tego problemu. Komputer stacjonarny z wieloma rdzeniami nie może rozwiązać tego problemu. Chmura nie może rozwiązać tego problemu. Nawet gdyby ktoś wymyślił komputer kwantowy, nadal nie byłby w stanie rozwiązać problemu z zatrzymaniem.

Streszczenie

W naszym badaniu teorii obliczalności zobaczyliśmy, że istnieje wiele funkcji, które nie są obliczalne w zwykłym znaczeniu tego słowa za pomocą argumentu zliczającego. Precyzyjnie zdefiniowaliśmy, co rozumiemy przez obliczenia, powracając do inspiracji Turinga z jego własnego doświadczenia z piórem i papierem w celu sformalizowania maszyny Turinga. Widzieliśmy, jak ten model może obliczyć wszystko, co każdy komputer dzisiaj lub wyobraża sobie na jutro, i zdaliśmy sobie sprawę z klasy problemów, które w ogóle nie są obliczalne.

Jednak obliczalność ma jednak wadę. To, że potrafimy rozwiązać problem, nie oznacza, że ​​możemy go rozwiązać szybko. W końcu, jaki jest pożytek z komputera, jeśli jego obliczenia nie skończą się, zanim Słońce zamieni się w nową za dziesiątki milionów lat w przyszłości?

Pozostawiając w tyle funkcje i języki obliczalne, omówimy teraz złożoność obliczeniową, badanie wydajności obliczeń i słynny problem P vs. NP.

Złożoność

Wolno kontra szybko

Informatycy rozpoznają różne klasy problemów, a dwie klasy, na których nam zależy, obejmują problemy, które komputery mogą rozwiązać szybko lub skutecznie, znane jako P , oraz problemy, których rozwiązania można szybko zweryfikować, ale nie można ich szybko uzyskać, znane jako NP .

Załóżmy na przykład, że jesteś odpowiedzialny za opracowanie algorytmów dla internetowego serwisu randkowego i ktoś zadaje pytanie: „Czy każdy może umówić się na randkę?” Odpowiedź sprowadza się do parowania kompatybilnych osób tak, aby wszyscy byli sparowani. Okazuje się, że istnieją wydajne algorytmy rozwiązania tego problemu. Ten problem jest w zestawie P .

A co, gdybyśmy chcieli zidentyfikować największą klikę wśród naszych użytkowników? Przez klikę rozumiemy największą sieć osób, które są ze sobą kompatybilne. Gdy liczba użytkowników jest niska, ten problem można szybko rozwiązać. Możemy łatwo zidentyfikować, powiedzmy, klikę z 3 użytkownikami. Jednak gdy zaczynamy szukać większych klik, problem staje się coraz trudniejszy do rozwiązania. Ten problem jest w zestawie NP .

Definicje formalne

P to zbiór problemów, które można rozwiązać w czasie wielomianowym. Oznacza to, że liczba kroków obliczeniowych jest ograniczona funkcją wielomianową w odniesieniu do rozmiaru problemu. Wiemy, że „Czy każdy może umówić się na randkę?” pytanie, znane również jako problem dopasowania dwuczęściowego, znajduje się w P .

NP to zbiór problemów, które można zweryfikować w czasie wielomianowym. Obejmuje to oczywiście każdy problem w P; jednak nie wiemy, czy to ograniczenie jest ścisłe. Wiemy o problemach, które można skutecznie zweryfikować, ale których nie da się skutecznie rozwiązać, ale nie wiemy, czy problem jest naprawdę nierozwiązywalny. Jednym z takich problemów jest problem kliki. Wiemy, że potrafimy sprawnie zweryfikować rozwiązanie, ale nie wiemy na pewno, czy potrafimy skutecznie rozwiązać problem.

Wreszcie, NP-zupełne to zestaw problemów, które są najtrudniejszymi problemami w NP . Są określane jako najtrudniejsze, ponieważ każdy problem w NP można skutecznie przekształcić w NPC . W rezultacie, gdyby ktoś miał znaleźć skuteczne rozwiązanie problemu w NPC , to cała klasa NP zostałaby wchłonięta przez P . Problem kliki jest również w NPC .

W ten sposób dochodzimy do problemu P vs. NP . Wielu informatyków i matematyków mocno wierzy, że P i NP nie są równe. Gdyby tak było, implikacje byłyby daleko idące. Znaczna część dzisiejszej infrastruktury cyfrowej opiera się na fakcie, że w NP występują problemy, których nie ma w P . Gdyby tak nie było, na przykład metody kryptograficzne załamałyby się z dnia na dzień, pozwalając osobie posiadającej skuteczne rozwiązanie problemu NPC na obalanie nawet najściślejszych protokołów bezpieczeństwa.

Subtelności podatności

Nowicjuszom informatyki różnica między problemami z dopasowywaniem a kliką może nie wydawać się wielkim problemem. W rzeczywistości różnica między problemem w P a problemem w NP może być bardzo subtelna. Umiejętność odróżnienia jest ważna dla każdego projektującego algorytmy w świecie rzeczywistym.

Rozważ problem z najkrótszą ścieżką. Biorąc pod uwagę dwie lokalizacje, celem jest zidentyfikowanie najkrótszej drogi między nimi. iPhone oblicza to w ciągu milisekund. Jest to problem wykonalny obliczeniowo.

Z drugiej strony rozważ problem komiwojażera, w którym celem jest odwiedzenie podzbioru możliwych miejsc docelowych kończących się na miejscu pochodzenia, podróżując jak najkrótszą odległość. Ten problem jest podobny do problemu najkrótszej ścieżki, ale jest NP-zupełny; wyjaśnia również, dlaczego logistyka łańcucha dostaw to branża warta miliardy dolarów.

W rzeczywistości możemy być jeszcze bardziej subtelni. Zamiast pytać o najkrótszą drogę (P), możemy poprosić o najdłuższą drogę bez cykli. Okazuje się, że problem najdłuższej ścieżki jest również NP-zupełny.

Istnieje wiele innych przykładów tego subtelnego rozróżnienia, w tym identyfikacja pokrycia wierzchołków w grafach dwudzielnych i ogólnych lub spełnianie formuł logicznych z dwoma lub trzema literałami w zdaniu. Chodzi o to, że nie jest od razu oczywiste, czy problem jest w P czy NP, i dlatego analiza czasu wykonywania jest umiejętnością krytyczną. Jeśli algorytm, który trzeba zaprojektować, dotyczy problemu w P, to wiemy, że istnieje efektywne rozwiązanie. Jeśli z drugiej strony problem jest w NP, to mamy mocne argumenty przeciwko szukaniu rozwiązania, ponieważ algorytm, ogólnie rzecz biorąc, po prostu zabierałby zbyt dużo czasu, aby rozwiązać problem.

Streszczenie

W tym badaniu złożoności zdefiniowaliśmy klasy problemów P i NP. P nieformalnie reprezentuje problemy, które można skutecznie rozwiązać za pomocą komputera, podczas gdy NP reprezentuje te, które można skutecznie zweryfikować.

Nikt nie był w stanie udowodnić, że P nie jest równe NP. To, czy te dwie klasy problemów są równoważne, jest znane jako problem P vs. NP i jest to najważniejszy otwarty problem współczesnej informatyki teoretycznej, jeśli nie w całej matematyce. W rzeczywistości w 2000 roku Clay Math Institute nazwał problem P vs. NP jako jedno z siedmiu najważniejszych otwartych pytań w matematyce i zaoferował nagrodę w wysokości miliona dolarów za dowód, który określa rozwiązanie tego problemu.

Wniosek

W tym artykule zagłębiliśmy się w obszary obliczalności i złożoności, odpowiadając na ważne pytania, takie jak „Czym jest komputer?” Chociaż szczegóły mogą być przytłaczające, warto pamiętać o kilku istotnych kwestiach:

• Są rzeczy, których po prostu nie da się obliczyć, na przykład problem z zatrzymaniem.

• Jest kilka rzeczy, których nie da się wydajnie obliczyć, na przykład problemy w NPC.

Ważniejsze od szczegółów są sposoby myślenia o obliczeniach i problemach obliczeniowych. W naszym życiu zawodowym, a nawet na co dzień, możemy natknąć się na problemy, których nigdy wcześniej nie widzieliśmy, i możemy użyć wypróbowanych i prawdziwych narzędzi i technik, aby określić najlepszy sposób działania.

Dalsza lektura na blogu Toptal Engineering:

• Jak podejść do pisania tłumacza od podstaw