Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS)

Odpowiedź: nieznana.

Zadawane pytania są naturalne, otwarte i pozornie trudne; pytanie jest teraz wiki społeczności.

Przegląd

Pytanie ma na celu podzielenie języków należących do klasy złożoności  - wraz z maszynami decyzyjnymi Turinga (TM), które akceptują te języki - na dwie uzupełniające się podklasy:$P$

• języki gnostyczne i bazy TM (które można zweryfikować / zrozumieć), w przeciwieństwie do
• kryptyczne języki i bazy TM (których nie można zweryfikować / zrozumieć).

Definicje: liczby gnostyczne a liczby tajemnicze , bazy TM i języki

W ramach aksjomatów PA i ZFC wyróżniamy gnostyczne od tajemniczych maszyn i języków Turinga w następujący sposób:

D0   Mówimy, że obliczalna liczba rzeczywista   jest gnostyczna , jeżeli jest powiązana z niepustym zestawem baz TM, przy czym każda baza TM jest określona w PA jako jawna lista liczb zawierająca prawidłowy kod na uniwersalnej bazie TM, tak że dla dowolnej dokładności ϵ > 0 dostarczone jako wejście, każda TM możliwa do udowodnienia (w ZFC) zatrzymuje się z liczbą wyjściową o, która w sposób możliwy do udowodnienia (w ZFC) spełnia r - ϵ < o $r$$\epsilon\gt0$$o$ .$r-\epsilon\lt o\lt r+\epsilon$

Uwaga   Wiadomo, że niektóre obliczalne liczby rzeczywiste nie są gnostyczne (konkretny przykład patrz Raphaela Reitziga na pytanie jkffa „ Czy istnieją dowody istnienia niekonstruktywnego algorytmu? ”). Aby uniknąć zmagania się z tymi liczbami obliczalnymi, ale niezręcznymi, nakłada się ograniczenie, aby wykładniki środowiska wykonawczego były obliczalne przez TM, które są jawnie wyliczone w PA (w przeciwieństwie do TM domyślnie określonych w ZFC). Dalsza dyskusja znajduje się w rozdziale Uwagi wstępne (poniżej).

Teraz szukamy definicji, które wychwytują intuicję klasy złożoności $P$ zawiera podzbiór języków tajemniczych , do których nie można przypisać żadnego (gnostycznego) wykładnika czasu wykonywania dolnej granicy.

Patrząc w przyszłość, ostateczna definicja ( D5 ) określa ideę kanonicznie tajemniczej decyzji TM , której definicja jest tworzona w celu uniknięcia redukcji, które (trywialnie) maskują tajemnicze obliczenia poprzez nałożenie obliczeniowych zbędnych obliczeń epi. Uzasadnienie i źródła tej kluczowej definicji omówiono później - pod nagłówkiem Rozważania końcowe  - i z wdzięcznością przyjmuje się komentarze Timothy Chowa, Petera Shora, Sasho Nikolova i Lucy Trevisana.

D1   Biorąc pod uwagę maszynę Turinga M, która zatrzymuje się dla wszystkich ciągów wejściowych, M jest nazywana tajemniczą iff, następujące stwierdzenie nie jest ani możliwe do udowodnienia, ani obalenia dla co najmniej jednej gnostycznej liczby rzeczywistej  :$r \ge 0$

Oświadczenie: Czas działania M wynosi w odniesieniu do długości wejściowej ${O}(n^r)$$n$

Maszyny Turinga, które nie są tajemnicze, mówimy, że są gnostycznymi TM.

D2   Mówimy, że decyzja maszyny Turinga M jest wydajna, jeśli ma gnostyczny wykładnik czasu wykonania  taki że język L, który akceptuje M, nie jest akceptowany przez żadną inną TM, która ma wykładnik czasu wykonania gnostyka mniejszy niż  r .$r$$r$

D3   Mówimy, że język L jest tajemniczy, jeśli jest akceptowany przez (a)  co najmniej jedną maszynę Turinga M, która jest zarówno wydajna, jak i tajemnicza, a ponadto (b)  żadna TM, która jest zarówno wydajna, jak i gnostyczna, akceptuje L.

Wyrazić D3 w inny sposób, język jest tajemniczy w bazach TM, które najskuteczniej akceptują ten język, same są tajemnicze.

Mówimy, że języki, które nie są tajemnicze językami gnostycznymi .

D4   Mówimy, że tajemnicza TM jest silnie tajemnicza, jeśli język, który akceptuje, jest tajemniczy.

D5   Mówimy, że silnie tajemnicza jest TM kanonicznie tajemnicza, jeśli jest wydajna.

Wyrazić D5 w inny sposób, każdy tajemniczy język jest akceptowany przez zestaw kanonicznie tajemniczych TM decyzji, które są najbardziej wydajnymi TM decyzjami, które akceptują ten język.

Zadawane pytania

Następująca hipoteza C0 jest naturalna i (najwyraźniej) otwarta:

C0   Klasa złożoności P zawiera co najmniej jeden tajemniczy język.

Trzy pytania są zadawane, Q1 - Q3 , z których pierwszy jest:

P1   Czy hipoteza C0 jest niezależna od PA lub ZFC?

Przy założeniu, że C0 jest prawdziwe - albo w ZFC, albo jako niezależny aksjomat uzupełniający ZFC - dwa kolejne pytania są naturalne:

Q2   Czy może być co najmniej jeden tajemniczy język w P może być konkretnie przedstawiony, to znaczy przedstawiony jako słownik wyraźnych słów w skończonym alfabecie, który zawiera wszystkie słowa o dowolnej określonej długości? Jeśli tak, pokaż taki słownik.

P3   Czy można przedstawić konkretnie co najmniej jedną kanonicznie tajemniczą decyzję TM, czyli jako opis umożliwiający zbudowanie fizycznej maszyny Turinga, która decyduje (w czasie wielomianowym) wszystkie słowa ze słownika Q2 ? Jeśli tak, zbuduj taką maszynę Turinga i obliczając ją, pokaż tajemniczy słownik języka z Q2 .

Uwagi dotyczące definicji

Definicja D0 oznacza, że ​​każda gnostyczna liczba rzeczywista jest obliczalna, ale wiadomo, że niektóre obliczalne liczby rzeczywiste nie są gnostyczne. Przykłady można znaleźć w odpowiedziach na MathOverflow autorstwa Michaëla Cadilhaca i Ryana Williamsa oraz na TCS StackExchange autorstwa Raphaela Reitziga . Mówiąc bardziej ogólnie, definicje D0 – D5 są tworzone w taki sposób, aby wykluczały odniesienia do wykładników wykonawczych innych niż gnostyczne.

Jak omówiono w wiki TCS „ Czy P zawiera niezrozumiałe języki? ”, Definicje D0 – D5 zapewniają, że każdy kryptyczny język jest akceptowany przez co najmniej jedną TM, która jest kanonicznie kryptyczna. (Zauważ też, że w obecnym pytaniu słowo „tajemnicze” zastępuje mniej opisowe słowo „niezrozumiałe” użyte w wiki).

Ponadto - w świetle D3 (a) i D3 (b)  - nie istnieje żadne obliczeniowo trywialne zredukowanie kanonicznie kryptycznej TM do gnostycznej TM, która w sposób możliwy rozpoznaje ten sam język. W szczególności D3 (a) i D3 (b) utrudniają strategie redukcji polilimiterów przedstawione w komentarzach Petera Shora i Sasho Nikolova oraz niezależnie przez Lucę Trevisana , a także utrudniają strategię redukcji wielomianu Timothy Chowa , wszystkie z których podobnie maskują tajemnicze obliczenia poprzez nałożenie obliczeniowego zbędnego epi-obliczenia .

Zasadniczo definicje „gnostyczny” i „tajemniczy” są celowo dostrojone, aby były solidne w odniesieniu do matematycznie trywialnych redukcji (i jest całkiem możliwe, że dalsze dostosowanie tych definicji może być pożądane).

Względy metodologiczne

Przegląd Lance'a Fortnowa „ Status problemu P w porównaniu z NP ” bada metody ustalania niezależności (lub innych) przypuszczeń w teorii złożoności; szczególnie pożądane są sugestie, w jaki sposób metody, które Lance recenzuje, mogą pomóc (lub nie) w odpowiedzi na pytanie 1 .

Oczywiste jest, że wiele dalszych pytań jest naturalnych. Np. Hipoteza Hartmanisa-Stearnsa inspiruje nas do pytania: „Czy istnieją tajemnicze maszyny Turing w czasie rzeczywistym? Czy ich istnienie (lub nie) jest niezależne od PA lub ZFC?”

Uwagi dotyczące typu Zeilbergera

W przypadku, gdy odpowiedź na pytanie 1 brzmi „tak”, wówczas wyrocznie decydujące o członkostwie w istnieją poza PA lub ZFC, a zatem nie wiadomo (obecnie), że istotnym elementem współczesnej teorii złożoności jest system formalny logika. $P$

Pod tym względem teoria złożoności różni się od większości dyscyplin matematycznych, tak że obawy wyrażone przez Dorona Zeilbergera w jego niedawnej „ Opinii 125: Teraz, gdy Alan Turing skończył 100 lat, nadszedł czas, aby rzucić nowe spojrzenie na jego wkład w sprawy seminarium , które przyniosły wiele dobrych, ale także wielu szkód ”, są prawdopodobnie uzasadnione.

Obawy Zeilbergera przybierają wyraźną formę jako kryterium Z0    (! Q1  ) i& (! C0  ), co jest równoważne z następującym kryterium:$\equiv$

Z0:   Kryterium wrażliwości Zeilbergera   Definicje klasy złożoności P   nazywane są wrażliwymi na Zeilbergera we wszystkich językach w P można udowodnić, że są gnostyczne.

Obecnie nie wiadomo, czy definicja złożoności P   według Stephena Cooka jest rozsądna ze względu na Zeilbergera.

Uwagi motywacyjne

Definicje „gnostyczny” i „tajemniczy” są tworzone z myślą o (ostatecznie) decydujących przypuszczeniach, takich jak:

C1   Niech i$P'$ będą ograniczeniami gnostycznymi P i N P odpowiednio. Zatem P ′ ≠ N P ′ jest albo możliwe do udowodnienia, albo można je obrócić w PA lub ZFC.$NP'$$P$$NP$$P' \ne NP'$

C2   (jak wyraźnie udowodniono w PA lub ZFC)$P' \ne NP'$

Oczywiście C2   C1 , i odwrotnie, można sobie wyobrazić, że dowód (meta) twierdzenia C1 może dostarczyć wskazówek w kierunku dowodu (silniejszego) twierdzenia C2 .$\to$ 

Ogólna motywacja to oczekiwanie / intuicja / nadzieja, że ​​w przypadku dobrze dostrojonego rozróżnienia między gnostycznymi a tajemniczymi TM i językami dowód C1, a nawet C2 może oświetlić - a nawet mieć porównywalne praktyczne implikacje - - przypuszczalnie o wiele trudniejszy i głębszy dowód, że . $P\ne NP$

Juris Hartmanis był jednym z pierwszych teoretyków złożoności, którzy poważnie kontynuowali tę linię dochodzenia; patrz na przykład monografia Hartmanisa Wykonalne obliczenia i możliwe do udowodnienia właściwości złożoności (1978).

Uwagi nomenklaturowe

Z Oxford English Dictionary (OED) mamy:

• gnostic (przym)  W odniesieniu do wiedzy; poznawczy; intelektualista   „Oni [liczby] istnieją w sposób witalny, gnostyczny i spekulacyjny, ale nie w sposób operacyjny”.

• cryptic (przym)  Nie od razu zrozumiałe; tajemniczy, zagadkowy   „Zamiast prostych zasad przydatnych ludzkości, oni [filozofowie] narzucają krucyfiks i mroczne zdania”.

Najwyraźniej żaden Przegląd Matematyczny nie używał wcześniej słowa „gnostyk” w jakimkolwiek sensie. Zwraca się jednak uwagę na najnowszy artykuł Marcusa Krachta „ Gnosis ” ( Journal of Philosophical Logic , MR2802332), który wykorzystuje sens OED.

Najwyraźniej żaden przegląd matematyczny nie użył słowa „tajemniczy” - w sensie technicznym - w odniesieniu do teorii złożoności. Należy jednak zwrócić uwagę na artykuł Charlesa H. Bennetta „ Głębokość logiczna i złożoność fizyczna ” (w Universal Turing Machine: A Half-Century Survey , 1988), który zawiera fragment

Innym rodzajem złożoności związanym z przedmiotem byłaby trudność, biorąc pod uwagę przedmiot, znalezienia prawdopodobnej hipotezy, aby to wyjaśnić. Obiekty o takiej złożoności można nazwać „tajemniczymi” : znalezienie wiarygodnego źródła dla obiektu jest jak rozwiązanie kryptogramu.

Względy natury, otwartości i trudności

Naturalność tych pytań ilustruje tezę monografii Jurisa Hartmanisa pt. Feasible Computations and Provable Complexity Properties (1978), która:

„Wyniki dotyczące złożoności algorytmów zmieniają się dość radykalnie, jeśli weźmiemy pod uwagę tylko właściwości obliczeń, które można formalnie udowodnić.”

Otwartość i trudność tych pytań jest zasadniczo zgodna z wnioskiem przeglądu Lance'a Fortnowa „ Status problemu P kontra NP ” (2009), który:

„Nikt z nas tak naprawdę nie rozumie problemu P kontra NP, dopiero zaczęliśmy obierać warstwy wokół tego coraz bardziej złożonego pytania”.

Wskazówki dotyczące Wiki

Szczególnie poszukiwane są korekty definicyjne i strategie dowodowe odnoszące się konkretnie do pytań Q1 – Q3 i szeroko wyjaśniające przypuszczenia typu Hartmanisa C1 – C2 .

Myślę, że istnieje zasadnicza podstawowa trudność z pytaniem, które tu zadajesz (i że zadałeś to pytanie w związku z niezrozumiałymi językami).

Z grubsza mówiąc, wydaje się, że szukasz języka $L$ takiego

ale ZFC nie wie, że L ∈ $L\in P$$L\in P$ .

Aby zrozumieć trudności z Twojego pytania, myślę, że trzeba najpierw zrozumieć, że istnieje zasadnicza różnica pomiędzy intensjonalnych i ekstensjonalnych definicji języka . Extensionally, L jest określana przez co słowa są czy nie są członkami L . Oznacza to, że dwa języki L i L ′ są zasadniczo równe wtedy i tylko wtedy, gdy zawierają dokładnie takie same słowa jak członkowie. W przeciwieństwie do tego, intensional definicja L opisuje pewne warunki dla słowo aby być w L . Maszyna Turinga, która akceptuje lub formuła pierwszego rzędu$L$$L$$L$$L$$L'$$L$$L$$L$ która obowiązuje wtedy i tylko wtedy, gdy x ∈ L , może być uważana za intensywną definicję$\phi(x)$$x\in L$$L$ .

Chodzi o to, że każdy który jest (przedłużająco) w P, przyjmuje niezwykle prosty opis, ponieważ P jest tak zwaną „złożoną” klasą złożoności. Mianowicie, wystarczy wziąć wielomianowo taktowaną maszynę Turinga, która kończy się dokładnie w pożądanym czasie. Każdy „rozsądny” system do wykonywania matematyki, taki jak PA lub ZFC, będzie w stanie udowodnić, że L ∈ P, jeśli użyjesz tego prostego opisu $L$$P$$P$$L\in P$$L$ .

Więc jeśli chcesz pomylić ZFC, będziesz musiał wymyślić (intensywny) opis który jest „zbyt skomplikowany”, aby ZFC mógł uznać go za równoważny z prostym opisem $L$$L$ . Jest to możliwe, ale w pewnym sensie zbyt łatwo jest być interesującym. Wszystko, co musisz zrobić, to wziąć coś, o czym wiemy, że ZFC nie rozumie (np. Własną spójność) i jakoś pomieszać go z definicją Na przykład, oto opis zestawu liczb całkowitych:$L$

$x$ jest parzyste, a nie koduje dowodu, że ZFC jest niespójny.$x$

Zakładając, że ZFC jest spójny, powyższa formuła określa zestaw parzystych liczb całkowitych, ale ZFC tego nie zna. Przy odrobinie majsterkowania możemy łatwo uzyskać opis zestawu liczb całkowitych, których ZFC nie będzie w stanie udowodnić, że jest w $P$ .

Rezultat jest taki, że jeśli masz nadzieję, że powodem, dla którego trudno jest udowodnić, że jest to, że istnieją języki w P, które są „zbyt skomplikowane”, abyśmy mogli o tym myśleć, to myślę, że źle szczekasz drzewo. Podsumowując, każdy język w P jest w P z trywialnych powodów. Możesz mętnieć wody, bawiąc się niemożliwie nieprzejrzystymi opisami języków w P , ale jest to ogólna sztuczka, która nie ma nic wspólnego z P , więc nie sądzę, że daje wiele wglądu.$P\ne NP$$P$$P$$P$$P$$P$

P1: $\:$Brak
Q2:$\:$ Tak, co najmniej dwa-1-binarne

Lemat: $\:$ Każda TM z obliczalnym wykładnikiem czasu wykonywania, który wynosi co najmniej 1, jest transcendentalna.

Dowód:
niech A i B będą rekurencyjnie nierozłącznymi zestawami .$\:$$M_0$$\:$$M_1$$\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$M_0$$M_1$$r_m$ jest niż negatywne i obliczalne i zawsze ma się [if$\:m\in A\:$ wtedy stwierdzenie D1 jest prawdziwe] i [if $\:m\in B\:$ wtedy stwierdzenie D1 jest fałszywe]. $\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$r_m$$\:$Dlatego maszyna Turinga jest transcendentalna.


Definicja:
co najmniej dwa-1-in-binarne to zbiór liczb całkowitych nieujemnych, których
reprezentacja binarna ma co najmniej dwie 1-y.$\:$ (założę się, że nigdy nie zgadłeś ^ _ ^)

Definicja:
M jest maszyną Turinga, która skanuje binarną reprezentację danych
wejściowych, akceptuje, jeśli znajdzie co najmniej dwa 1, i odrzuca inaczej.

Oczywiście M decyduje o wartości co najmniej dwa-1-in-binarne i ma wykładnik czasu działania 1, a żadna inna maszyna Turinga z mniejszym wykładnikiem czasu wykonywania również nie decyduje o co najmniej dwóch-1-sekundach binarnych.
Trywialnie$\: 1\leq 1 \:$$1$$\;\;$Na mocy lematu M jest skuteczny i transcendentalny.
Te średnie co najmniej dwa-1-binarne są również transcendentalne.

Dlatego TPCCC jest twierdzeniem PA (i ZFC), a
co najmniej dwa-1-in-binarne jest konkretnym językiem transcendentalnym.

Definicja 1: Niech $x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$. Clearly, we can build a Turing machine which, given $n$, will compute $x_n$. Also the $x_n$ converge to $x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$.

So $x$ is a gnostic real, which is equal to 2 if and only if $\bf{ZF}$ is consistent.

Definition 2: For any gnostic real $x > 1$, let $M'_x$ be a Turing machine which takes an index $n$ of a Turing machine $N$ and an input $s$, simulates $N$ on $s$ for $|s|^x/\log(|s|)$ steps (this function is time-constructible, because $x$ is gnostic), and inverts the result. By the Recursion Theorem, we may choose $M_x$ to be $M'_x$ with a fixed index of $M_x$ as its first input. Then a standard argument (the Time Hierarchy Theorem) shows that $M_x$ has runtime $\mathcal O(|s|^y)$ precisely when $y\ge x$, and that $M_x$ is efficient for its language.

Therefore, for $x$ as in Definition 1, $M_x$ will run in time $\mathcal O(|s|^2)$ precisely if $x = 2$, ie if $\bf{ZF}$ is consistent; moreover this fact will itself be provable in $\bf ZF$. So [if $\bf ZF$ is consistent], $M_x$ is a [strongly and canonically] cryptic machine, and this fact will be provable in $\bf ZF + Con(\bf ZF)$.

However, $\bf ZF + \not Con(\bf ZF)$ proves that all languages in $\bf P$ are gnostic, since it proves that $\bf ZF$ proves that every language has runtime $\mathcal O(|s|^z)$ for every $z$. So it is undecidable in $\bf ZF$ whether any cryptic language exists.

To answer your second and third questions, the definition I gave above for $M_x$ is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.