Czy P zawiera niezrozumiałe języki? (Wiki społeczności TCS)

Odpowiedź: nieznana

Ogromne podziękowania dla wszystkich, którzy pomogli dopracować to pytanie i związane z nim definicje.

Definicje tej wiki stanowiły punkt wyjścia dla najnowszej wiki TCS „ Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS) ”.

Preferowana jest nowsza wiki, ponieważ jej definicje i nazewnictwo są znacznie bardziej wyrafinowane niż w przypadku tej starszej wiki.

W szczególności, nomenklatura tej starszej wiki niezrozumiała Języki zrozumiałe dla i TM są zastępowane w nowszej wiki przez cryptic gnostic . Poza szczegółowymi definicjami - które jednak są ważne - dwie strony wiki poruszają podobną klasę pytań. $\Leftrightarrow$ $\Leftrightarrow$

Dalsze odpowiedzi są mile widziane

Dalsze odpowiedzi są mile widziane (nie trzeba dodawać) i prawdopodobne jest, że dalsze dostosowanie definicji jest właściwe. Jedną z głównych lekcji jest to, że ta klasa pytań jest trudna do sformułowania, a jeszcze trudniejsza jest rygorystyczna odpowiedź.

Jako tło odpowiedź Sasho Nikolova została oceniona jako „zaakceptowana”, ponieważ dostarczyła sformułowania, które uchwyciło cel pytania: odpowiedź na pytanie (najwyraźniej) nie jest znana.

Cenna odpowiedź Philipa White'a uzasadniła stopniową definicję TM, które są niezrozumiałe w porównaniu z silnie niezrozumiałymi, w porównaniu z kanonicznie niezrozumiałymi (według listy „stopniowe definicje niezrozumiałości” poniżej).

Poniższe stwierdzenie pytania zawiera tymczasowo cenne spostrzeżenia i sugestie dostarczone przez Tsuyoshi Ito, Marzio De Biasi, Hucka Bennetta, Ricky'ego Demera, Petera Shora, a także cenny post na blogu autorstwa Lucy Trevisana .

Formalna definicja

Niezrozumiałe maszyny Turinga są zdefiniowane (w ramach ZFC) w następujący sposób:

D1 Biorąc pod uwagę maszynę Turinga M, która zatrzyma się w sposób ciągły dla wszystkich łańcuchów wejściowych, M jest nazywana niezrozumiałą iff, następujące stwierdzenie nie jest ani możliwe do udowodnienia, ani możliwe do obalenia dla co najmniej jednej dodatniej półfinalnej liczby rzeczywistej : $r$

Instrukcja: Środowisko wykonawcze M ma wartość w odniesieniu do długości wejściowej ${O}(n^r)$ $n$

I odwrotnie, M nazywa się zrozumiałym, jeśli nie jest niezrozumiałe.

Jednoznaczne rozstrzygalne

Wpis w Wikipedii „ Problem nierozstrzygalny: Przykłady stwierdzeń nierozstrzygalnych ” zwięźle analizuje różne zmysły terminu „nierozstrzygalne”, które są zwyczajowo stosowane w literaturze teoretycznej i teoretycznej. Aby uniknąć dwuznaczności, w definicjach i pytaniach zastosowano wyłącznie terminologię „ani do udowodnienia, ani do obalenia”.

Dalsze odniesienia w tym względzie to notatki z kursu Jeremy'ego Avigada „ Niekompletność przez problem zatrzymania ”, esej Scotta Aaronsona na blogu „ Twierdzenie Rossera przez maszyny Turinga ” oraz wpis na blogu Lucy Trevisan Dwa interesujące pytania .

O istnieniu niezrozumiałych maszyn Turinga

To, że istnieją niezrozumiałe maszyny Turinga, wynika konkretnie z konstrukcji Emmanuele Violi i ogólnie z teorii złożoności Jurisa Hartmanisa. W szczególności konstrukcja Violi zapewnia, za pomocą metod notatek kursowych Jeremy'ego Avigada (jak je rozumiem), następujący lemat:

Lemma [Implikacja Violi]
(jeśli język L jest akceptowany przez zrozumiałą bazę TM) (L jest akceptowany przez niezrozumiałą bazę TM). $\to$

Poszanowanie natury w definiowaniu niezrozumiałości

Naturalne jest zastanawianie się, czy odwrotna implikacja do Implikacji Violi jest prawdziwa.

Względy natury wymagają ostrożnego przedstawienia odwrotnej implikacji, ponieważ poniższy komentarz Philipa White'a pokazuje, jak w sposób trywialny zredukować niezrozumiałe TM do zrozumiałych TM przez polilimitery , które są modułami obliczeniowymi, które (w efekcie) „ wypełniają ” czas działania niezrozumiałej maszyny, więc aby sprowadzić go do zrozumiałej maszyny.

W szczególności naturalne jest wymaganie, aby nie „ nieestetycznie maskować starych elementów niezrozumiałości poprzez wprowadzenie nowych elementów niezrozumiałości ”. Kluczowym wyzwaniem związanym z zadanym pytaniem jest: „Czy istnieje naturalna definicja niezrozumiałości?” … Które (biorąc pod uwagę dyskusję TCS) powinniśmy być może uznać za nietrywialne meta-pytanie, które może mieć więcej niż jedną naturalną odpowiedź.

W związku z tą wiodącą zasadą natury, stopniowe definicje niezrozumiałości są określone w następujący sposób.

Stopniowe definicje niezrozumiałości

D2 Mówimy, że maszyna Turinga M jest wydajna, jeśli ma wykładnik czasu działania tak że język L, który akceptuje M, nie jest akceptowany przez żadną inną TM, która ma wykładnik czasu działania mniejszy niż . $r$ $r$

D3 Mówimy, że język L jest niezrozumiały, jeśli jest akceptowany przez (a) co najmniej jedną maszynę Turinga M jest zarówno wydajną, jak i niezrozumiałą, a ponadto (b) nie ma wydajnej i zrozumiałej bazy TM, która byłaby w stanie zaakceptować (w ZFC) L.

D4 Mówimy, że niezrozumiała TM jest bardzo niezrozumiała, jeśli język, który akceptuje, jest niezrozumiały.

D5 Mówimy, że silnie niezrozumiała TM jest kanonicznie niezrozumiała, jeśli jest skuteczna.

Definicje te zapewniają, że każdy niezrozumiały język jest akceptowany przez co najmniej jedną TM, która jest kanonicznie niezrozumiała, a ponadto - w świetle D3 (a) i D3 (b) - nie istnieje trywialna redukcja polilimitera kanonicznie niezrozumiałej TM do zrozumiałej TM który prawdopodobnie rozpoznaje ten sam język.

Trzy zadane pytania

P1 Czy klasa złożoności P zawiera niezrozumiałe języki?

Q2 Czy można konkretnie przedstawić co najmniej jeden niezrozumiały język? (jeśli tak, podaj konstruktywny przykład).

P3 Czy można konkretnie przedstawić co najmniej jedną kanonicznie niezrozumiałą bazę TM? (jeśli tak, podaj konstruktywny przykład).

Motywacja

Niezrozumiałe właściwości klasy złożoności P utrudniają zrozumienie szerokiej klasy problemów, które (dla pierwotnego twórcy tego pytania ) obejmują Puzzle Niebieskookich Wyspiarzy Terry'ego Tao, Grę Dicka Liptona i Urna- Kena Regana oraz ich hybrydyzację w kontekst Paradoksu Newcomba w grze Balanced Advantage Newcomb .

Jak podaje monografia Jurisa Hartmanisa Możliwe obliczenia i możliwe do udowodnienia właściwości złożoności (1978):

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ć.

Walka o skonstruowanie dobrze sformułowanych definicji i postulatów, które wychwytują wgląd Hartmanisa, pomaga nam lepiej zrozumieć, że klasa złożoności P ma w sobie kilka wyjątkowo osobliwych języków, które są rozpoznawane przez wyjątkowo osobliwe maszyny Turinga, których właściwościami jesteśmy (obecnie ) bardzo daleko od chwytania. Uderzające jest to, że w całkowicie rygorystycznym sensie nie wiadomo obecnie, czy klasa złożoności P jest zrozumiała.

Dziękujemy wszystkim, którzy wnieśli komentarze i odpowiedzi.

cc.complexity-theory complexity-classes turing-machines decidability John Sidles
źródło

Proszę zdefiniować termin „(maszyna Turinga), w sposób wyraźny w P.”

Tsuyoshi Ito

W problemie podanym w definicji „niezrozumiałe w P” jakie dokładnie są dane wejściowe? Czy maszyna Turinga jest częścią wejścia, czy jest stała? Ponadto, w jaki sposób podaje się liczbę rzeczywistą jako ciąg?

Tsuyoshi Ito

Obawiam się, że definicja nie ma sensu. Redukcja Violi pokazuje, że gdy maszyna Turinga jest częścią wejścia wraz z

, jej czas działania jest nierozstrzygalny. Ale jeśli wyjmiemy maszynę Turinga z wejścia i naprawimy język dla dowolnej maszyny Turinga, wówczas problem stanie się rozstrzygalny (ponieważ możemy zbudować decydującą TM specjalnie dla maszyny Turinga

r

$r$

M

$M$

Sasho Nikolov

Jak Sasho wyjaśnił zapobiegawczo, problem podany w definicji „niezrozumiały” w wersji 4 jest rozstrzygalny dla każdego M. Obawiam się, że popełniacie tutaj elementarny błąd. Jeśli nadal masz problemy ze zrozumieniem, ten post Raphaela i znajdujący się w nim link może być pomocny. Głosowałem za zamknięciem tego, ponieważ nie jest to prawdziwe pytanie.

Tsuyoshi Ito

Twoja definicja jest nadal zła. Biorąc pod uwagę niezrozumiałą maszynę Turinga w P, możesz przekształcić ją w zrozumiałą maszynę Turinga w P, umieszczając na niej licznik czasu, który liczy

kroków, a jeśli do tego czasu się nie zatrzyma, zatrzymuje go i odrzuca. Dla każdej niezrozumiałej maszyny Turinga w P istnieje

która zamieni ją w zrozumiałą maszynę Turinga akceptującą ten sam język. Oczywiście nie możesz udowodnić, że akceptuje ten sam język i nie możesz znaleźć odpowiednich wartości C i k , ale nie widzę, jak możesz to włączyć do swojej definicji.

C n^{k}

$Cn^k$

C

$C$

k

$k$

Peter Shor

Odpowiedzi:

(Odchodzę na emeryturę, ponieważ nie ma już znaczenia część odpowiedzi, która właśnie wyjaśniała, dlaczego nie ma nierozstrzygalnych przypadków problemu / brak algorytmów czasu policyjnego z nieobliczalnym ograniczeniem czasowym)

$T$ $M$ $M$ $T$

$M$ $M$
$M$ $M'$

Wygląda więc na to, że odpowiedź na twoje pytanie brzmi „nie”: każdy język rozstrzygalny w polityce czasowej przez jakąś maszynę jest ustalany przez sprawdzalną maszynę politytime. Ale może twoje pytanie powinno brzmieć:

$M$ $M'$ $M$

Podejrzewam, że odpowiedź brzmi „tak”, ale w tej chwili nie mam już czasu na poświęcanie się temu.

Sasho Nikolov
źródło

------ Istnieją dwa różne znaczenia tego słowa nierozstrzygalnego w matematyce i informatyce. Pierwszym z nich jest sens teoretyczny stosowany w odniesieniu do twierdzeń Gödla, że stwierdzenie nie jest ani możliwe do udowodnienia, ani do obalenia w określonym systemie dedukcyjnym. ... Z powodu dwóch znaczeń słowa „nierozstrzygalne” termin „ niezależny” jest czasami używany zamiast niezdecydowanego w znaczeniu „ani do udowodnienia, ani do obalenia”.

John Sidles,

Dzięki, Sasho! Doszedłem również do tego uznania, ale postulat ten można zmienić za pomocą rozróżnienia Wikipedii: „Istnieją dwa wyraźne znaczenia słowa nierozstrzygalnego w matematyce i informatyce. Pierwszym z nich jest sens teoretyczny używany w odniesieniu do twierdzeń Gödla, stwierdzenie, że stwierdzenie nie jest ani możliwe do udowodnienia, ani do obalenia w określonym systemie dedukcyjnym ... Z powodu dwóch znaczeń słowa „nierozstrzygalne” termin „ niezależny” jest czasem używany zamiast niezdecydowanego w znaczeniu „ani do udowodnienia, ani do odrzucenia”. Mam więc nadzieję, że wyjaśnię to pytanie dzisiaj.

John Sidles,

Poddany w dużej mierze twoim przemyślanym komentarzom dwuznaczny atrybut „rozstrzygalny” został teraz zastąpiony przez (miejmy nadzieję jednoznaczny) atrybut „ani do udowodnienia, ani do obalenia”. Za co doceniamy twoją pomoc i dziękuję.

John Sidles,

proszę sprawdzić moją zaktualizowaną odpowiedź

Sasho Nikolov

Dziękuję, Sasho. Ja również muszę zrobić sobie przerwę do jutra, jednak przy pierwszym czytaniu twoja sugestia wydaje się bardzo owocna i mam nadzieję, że wkrótce odpowiem na nią. Dzięki jeszcze raz.

John Sidles

Tylko rozszerzony komentarz próbujący zinterpretować pytanie.

$M$ ~~zapowiada się zatrzymać~~ $M$ ~~dodatnia liczba rzeczywista półfinałowa~~ $r$ ~~pytanie~~ $Q_{M,r}$

OPCJA 1

$Q_{M,r}(n)$ $M$ $n^r$ $n$

$2^n$ $M$ $\Rightarrow$

OPCJA 2

$Q_{M,r}$ $M$ $O(n^r)$

$\Rightarrow$

A jeśli zapytasz: „Ok, ale czy możemy obliczyć wartość 1 lub 0, aby zbudować algorytm, który odpowiada na pytanie dotyczące Opcji 2?”, Powracamy do tego:

$Q_{r}(M)$ $M$ $O(n^r)$ $M$

Marzio De Biasi
źródło

Marzo, dziękuję za tę odpowiedź i za komentarz powyżej. Dwuznaczny termin „rozstrzygalny” został już porzucony --- oznaczał różne rzeczy dla różnych społeczności --- na rzecz teoretycznego idiomu „ani do udowodnienia, ani do obalenia”. Do kolejki wyjaśniania poprawek do jutrzejszej wersji pytania (która, mam nadzieję, będzie ostatecznym rygorystycznym postawieniem pytania), zostanie dodana fraza „For all n ”, zgodnie z Twoją Opcją 1. I wreszcie, podziękowania i podziękowania zostały przedłużone tobie i wszystkim, za pomoc w postawieniu pytania rygorystycznie i jasno.

John Sidles

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Marzo, OK i dziękuję. Ponadto, aby ustalić „Implikację Violi”, musimy dołączyć argument z sekcji 3 notatek Jeremy'ego Avigada (połączonych w pytaniu) z konstrukcją Violi… zmienione pytanie wyjaśni tę kwestię. Nie trzeba dodawać, że proces wyjaśniania definicji był 10X ++ bardziej uciążliwy, niż początkowo się spodziewałem ... co może być głównym punktem pytania. Dzięki jeszcze raz.

John Sidles

Odpowiedź na twoje pytanie nr 1 brzmi zdecydowanie „nie”. Jak sądzę, ktoś wskazał w sekcji (bardzo długich) komentarzy, możesz łatwo dodać „polilimiting” do maszyny. Oznacza to, że nawet jeśli nie wiesz, co to jest r, jeśli zgadniesz liczbę całkowitą większą niż r (jest to oczywiście możliwe, oczywiście), możesz ustawić maszynę górną, która symuluje swoją „niezrozumiałą” maszynę Turinga, i wymusić ją aby przestać działać w czasie wielomianowym ... bez zmiany języka akceptowanego przez maszynę Turinga. W ten sposób można przekształcić dowolną „niezrozumiałą” wielomianową maszynę Turinga w czasową w „zrozumiałą” wielomianową maszynę Turinga w czasie, co oznacza, że nie ma języka w P, który byłby rozstrzygany wyłącznie przez „niezrozumiałe” maszyny Turinga.

Mam nadzieję, że to pomoże. O ile nie błędnie zinterpretowałem twoje pytanie i twoją intencję, moja odpowiedź jest z pewnością poprawna; to wcale nie jest otwarte pytanie.

Philip White
źródło

Nawiasem mówiąc, jeśli chcesz dobrego przykładu kandydata na tak zwany „niezrozumiały” algorytm, zobacz scholarpedia.org/article/Universal_search . Uniwersalny algorytm wyszukiwania dla rozwiązania SAT jest zgodny z twoją definicją niezrozumiałego iff P = NP jest formalnie niezależny.

Philip White

czy wiesz coś na temat ostatniego pytania z mojej odpowiedzi? Uważam, że to jedyne pytanie, które wciąż nie jest oczywiście trywialne .. dla mnie to jest

Sasho Nikolov

@Philip White, definicja jest starannie skonstruowana, aby uniknąć podanej przez ciebie konstrukcji. Ponieważ przypuśćmy, że środowisko wykonawcze M jest nierozstrzygalne dla jakiegoś wykładnika r , i przypuszczamy, że wartość r ' > r , i instalujemy r' -polilimiter w zmodyfikowanej maszynie M ', która rozpoznaje ten sam język co M, a następnie dla M' instrukcja „czas działania M 'wynosi O (n ^ r) w odniesieniu do długości wejściowej n” nadal jest nierozstrzygalny. Zgadzam się jednak, że musimy dokładnie przemyśleć, czy WSZYSTKIE gry kotów i myszy z polilimiterami określonymi przez wyrocznię są wykluczone (zgodnie z intencją) --- i dlatego głosowałem za odpowiedzią!

John Sidles

Aha, a ponieważ komentarz Sasho pokrywał się z moim, proszę pozwolić mi wyrazić uznanie dla ostatniego pytania w odpowiedzi Sasho , które (zgodnie z moim obecnym rozumieniem tego) w sposób sztuczny utrudnia wprowadzenie polilimiterów pochodzących z wyroczni. Tak jak poprzednio, będę musiał o tym pomyśleć przez dzień lub dwa. Jeszcze raz dziękuję, Philip.

John Sidles

Przepraszam, powinienem uważniej przeczytać odpowiedź Sasho Nikolova; Właśnie zobaczyłem słowo „tak”, ups. Za chwilę spojrzę na ostatnie pytanie i zobaczę, czy mam coś przydatnego do powiedzenia.

Philip White