Rozszerzona teza kościelna

Jednym z najczęściej dyskutowanych pytań na stronie było to, co oznaczałoby obalenie tezy Kościoła . Wynika to częściowo z faktu, że Dershowitz i Gurevich opublikowali w 2008 r. Dowód, że teza Kościoła to Biuletyn Symboliki Logicznej. - bezwstydna autopromocja - napisałem wpis na blogu ).

To pytanie dotyczy rozszerzonej tezy Kościoła-Turinga, którą sformułował Ian Parberry:

Czas na wszystkich „rozsądnych” modelach maszyn jest związany z wielomianem.

Dzięki Giorgio Marinelli dowiedziałem się, że jeden ze współautorów poprzedniego artykułu, Dershowitz i jego doktorant, Falkovich, opublikowali dowód Rozszerzonej tezy Turinga Kościoła, która właśnie ukazała się na warsztacie Rozwój Modele obliczeniowe 2011 .

Właśnie wydrukowałem papier dziś rano i przejrzałem go, nic więcej. Autorzy twierdzą, że maszyny Turinga mogą symulować dowolne sekwencyjne urządzenie obliczeniowe z co najwyżej wielomianowym obciążeniem. Obliczenia kwantowe i obliczenia równoległe na dużą skalę nie są wyraźnie uwzględnione. Moje pytanie dotyczy następującego oświadczenia w pracy.

Wykazaliśmy - jak przypuszczano i powszechnie uważa się - że każda skuteczna implementacja, niezależnie od używanych struktur danych, może być symulowana przez maszynę Turinga, co najwyżej wielomianowy narzut w złożoności czasowej.

Moje pytanie: czy to naprawdę „powszechnie się wierzy”, nawet w przypadku „prawdziwie” obliczeń sekwencyjnych bez randomizacji? Co jeśli rzeczy są losowe? Obliczenia kwantowe byłyby prawdopodobnie kontrprzykładem, gdyby w rzeczywistości można je utworzyć, ale czy istnieją możliwości „słabsze” niż kwant, który byłby również kontrprzykładem?

Rant przygotowawczy

Muszę ci powiedzieć, że nie rozumiem, jak mówienie o „dowodach” CT lub ECT dodaje światła do tej dyskusji. Takie „dowody” są zwykle tak dobre, jak założenia, na których się opierają - innymi słowy, co oznaczają słowa „obliczenia” lub „wydajne obliczenia”. Dlaczego więc nie przystąpić od razu do dyskusji na temat założeń i zrezygnować ze słowa „dowód”?

Tak było już z oryginalnym CT, ale z ECT jest jeszcze wyraźniej - ponieważ ECT jest nie tylko „filozoficznie nie do udowodnienia”, ale dziś powszechnie uważa się, że jest fałszywy! Dla mnie obliczenia kwantowe to olbrzymi, rażący kontrprzykład, który powinien być punktem wyjścia dla każdej współczesnej dyskusji na temat ECT, a nie czymś, co odsuwa się na bok. Jednak artykuł Dershowitza i Falkovicha nawet nie dotyka QC aż do ostatniego akapitu:

Powyższy wynik nie obejmuje obliczeń równoległych na dużą skalę, takich jak obliczenia kwantowe, ponieważ zakłada, że ​​istnieje ścisła granica stopnia równoległości z liczbą terminów krytycznych ustalonych przez algorytm. Kwestia względnie [sic] złożoności modeli równoległych będzie rozpatrywana w najbliższej przyszłości.

Uznałem powyższe za bardzo mylące: QC nie jest „modelem równoległym” w żadnym konwencjonalnym sensie. W mechanice kwantowej nie ma bezpośredniej komunikacji między „równoległymi procesami” --- tylko interferencja amplitud --- ale łatwo jest również wygenerować wykładniczą liczbę „równoległych procesów”. (Rzeczywiście, każdy system fizyczny we wszechświecie mógłby myśleć tak, jak to robimy!) W każdym razie, cokolwiek myślisz o interpretacji mechaniki kwantowej (lub nawet jej prawdzie lub fałszu), jasne jest, że wymaga ona osobnego dyskusja!

A teraz przejdź do (interesujących) pytań!

Nie, nie znam żadnych przekonujących kontrprzykładów do ECT innych niż obliczenia kwantowe. Innymi słowy, gdyby mechanika kwantowa była fałszywa (w sposób, który wciąż utrzymywał wszechświat bardziej „cyfrowy” niż „analogowy” w skali Plancka - patrz poniżej), wówczas ECT, jak rozumiem, nadal nie byłby „dający się udowodnić” (ponieważ nadal będzie zależał od faktów empirycznych na temat tego, co można skutecznie obliczyć w świecie fizycznym), ale byłaby to dobra hipoteza robocza.

Randomizacja prawdopodobnie nie stanowi wyzwania dla ECT, ponieważ jest ona powszechnie rozumiana, ze względu na mocne dowody, że P = BPP. (Pamiętaj jednak, że jeśli interesują Cię ustawienia inne niż problemy z decyzjami językowymi --- na przykład problemy z relacjami, drzewa decyzyjne lub złożoność komunikacji --- to losowość może mieć ogromne znaczenie. I te ustawienia są całkowicie rozsądne o których warto porozmawiać; po prostu nie są to ludzie, o których zwykle myślą, omawiając ECT).

Inna klasa „kontrprzykładów” do ECT, która jest często podnoszona, obejmuje przetwarzanie analogowe lub „hiper”. Moim zdaniem, według naszego najlepszego rozumienia fizyki obliczenia analogowe i hiperkomputerowe nie mogą być skalowane, a powodem, dla którego nie mogą, o ironio, jest mechanika kwantowa! W szczególności, chociaż nie mamy jeszcze kwantowej teorii grawitacji, to, co jest dziś znane, sugeruje, że istnieją fundamentalne przeszkody w wykonywaniu więcej niż około 10 ⁴³ kroków obliczeniowych na sekundę lub rozwiązywaniu odległości mniejszych niż około 10 ^-33 cm.

Na koniec, jeśli chcesz wyciągnąć z dyskusji wszystko, co może być prawdopodobnym lub interesującym wyzwaniem dla ECT i pozwolić na szeregowe, dyskretne, deterministyczne obliczenia, to zgadzam się z Dershowitzem i Falkovichem, że ECT ma to miejsce! :-) Ale nawet tam trudno wyobrazić sobie „formalny dowód”, który zwiększyłby moje zaufanie do tego stwierdzenia - prawdziwym problemem jest to, co bierzemy za słowa „seryjny”, „dyskretny” i „deterministyczny” myśli .

Co do twojego ostatniego pytania:

Obliczenia kwantowe byłyby prawdopodobnie kontrprzykładem, gdyby w rzeczywistości można je utworzyć, ale czy istnieją możliwości „słabsze” niż kwant, który byłby również kontrprzykładem?

Obecnie istnieje wiele interesujących przykładów systemów fizycznych, które wydają się być w stanie zaimplementować niektóre obliczenia kwantowe, ale nie wszystkie (dając klasy złożoności, które mogą być pośrednie między BPP i BQP). Co więcej, wiele z tych systemów może być łatwiejszych do zrealizowania niż pełna, uniwersalna kontrola jakości. Zobacz na przykład ten artykuł Bremnera, Jozsy i Shepherda lub ten autorstwa Arkhipova i mnie.

Ta odpowiedź ma stanowić uzupełnienie odpowiedzi Scotta Aaronsona (z którą głównie się zgadzam).

Z inżynieryjnego punktu widzenia uderzające jest to, że artykuł Dershowitz / Falkovich używa słowa „losowy” tylko w znaczeniu „pamięci o swobodnym dostępie”, a ponadto artykuł nie używa słowa „próbka” (ani żadnego z jego warianty) w ogóle. Analiza Dershowitza / Falkovica skupia się raczej wyłącznie na obliczeniach funkcji numerycznych.

To ograniczenie jest uderzające, ponieważ ogromna większość współczesnych zasobów obliczeniowych STEM (zaryzykuję stwierdzenie) nie przestrzega ograniczeń funkcji numerycznych, ale raczej zajmuje się generowaniem próbek z rozkładów (np. Dynamiki molekularnej, turbulentnego przepływu płynu, propagacji pękania , hałaśliwe systemy spinowe zarówno klasyczne, jak i kwantowe, fale propagowane przez losowe media itp.).

Tak więc, jeśli „rozszerzona teza Kościoła” (ECT) ma mieć istotne znaczenie dla szeroko zdefiniowanych obliczeń STEM, być może należy znieść wyłączne ograniczenie funkcji numerycznych i podać ogólne stwierdzenie ECT, które obejmuje pobieranie próbek obliczenia (oraz ich weryfikacja i weryfikacja).

Czy ta uogólniona wersja próbkowania ECT nadal byłaby objęta zakresem TCS, jak tradycyjnie pojmowano? Najwyraźniej odpowiedź brzmi „tak”, zgodnie z często zadawanymi pytaniami dotyczącymi wymiany stosów TCS :

Odsyłamy do opisu Grupy Specjalnych Zainteresowań ACM ds. Algorytmów i Teorii Obliczeń (SIGACT) ... TCS obejmuje szeroki zakres tematów, w tym obliczenia probabilistyczne ... Praca w tej dziedzinie [TCS] często wyróżnia się naciskiem na matematykę technika i dyscyplina.

$\text{ECTT}$$\{0,1,+,\times\}$$\text{ECTT}$, który mówi, że ten predykat racjonalności jest spełniony przez dokładnie te modele, które mają wielomianowe tłumaczenie czasowe na maszynę Turinga. Jako aksjomat nie można go sfalsyfikować w tym sensie, że nasza teoria jest w stanie temu zaprzeczyć, o ile teoria była na początku spójna, ale zasadność naszej teorii jest falsyfikowalna: możliwe, że istnieje rozsądny model obliczeń niezwiązany z Maszyny Turinga przez wielomianowe tłumaczenie czasowe. Pozwolenie, że to hipotetyczne odkrycie może wymagać zmiany myślenia o tym, co jest rozsądne, tak postrzegam stronę formalną. Z perspektywy czasu wydaje się to trywialne, ale myślę, że należy oddzielić matematykę od wszystkiego innego.

$\text{ECTT}$$\text{BPP}$$\text{P}$$\text{ECTT}$$\text{P} \neq \text{BPP}$$\text{BPP}$$\text{ECTT}$$\text{P}$$\text{ECTT}$$\text{P} \neq \text{BQP}$$\text{ECTT}$$\text{ECTT}$$\text{BPP}$$\text{BQP}$$\text{P}$

Załóżmy na przykład, że twierdzę, że zbudowałem maszynę, która uwzględnia liczby, i że jej środowisko wykonawcze spełnia określoną granicę wielomianową. Maszyna jest w pudełku, podajesz numer zapisany na papierowej taśmie i drukuje czynniki. Nie ma wątpliwości, że to działa, ponieważ użyłem go do wygrywania wyzwań RSA, konfiskaty kryptowaluty, liczenia wybranych liczb itp. Co znajduje się w pudełku? Czy to jakiś niesamowity nowy typ komputera, czy może zwykły komputer z niesamowitym nowym typem oprogramowania?

$\text{ECTT}$$\text{ECTT}$

$\text{ECTT}$$\text{EXPTIME}$$\text{P}_\text{CTC} = \text{PSPACE}$$\text{ECTT}$$\text{P} \neq \text{PSPACE}$

$\text{P} \neq \text{NP}$$\text{ECTT}$$\text{P} \neq \text{P}_\text{CTC}$$\text{P} = \text{NP}$$\text{ECTT}$$\text{ECTT}$$\text{NP}$$\text{3SAT}$$\text{P}$

$\text{EXPTIME}$$\text{ECTT}$$\text{EXPTIME} \neq \text{P}$$\text{ECTT}$

$\text{ECTT}$$\text{P} = \text{BPP}$$\text{ECTT}$$\text{P} \neq \text{BQP}$

$\text{ECTT}$$\{\in\}$$\text{ECTT}$$\{\in\}$

$\text{ECTT}$