Zadane pytanie dotyczy tego, czy rozstrzygające jest następujące pytanie:
Problem Biorąc pod uwagę liczbę całkowitą i maszynę Turinga która ma być w P, to czy środowisko wykonawcze w odniesieniu do długości wejściowej ?M M O ( n k ) n
Dopuszczalna jest wąska odpowiedź „tak”, „nie” lub „otwarta” (z odniesieniami, szkicem dowodowym lub przeglądem obecnej wiedzy), ale szersze odpowiedzi są również bardzo mile widziane.
Odpowiedź
Emanuele Viola opublikował dowód, że pytanie jest nierozstrzygalne (patrz poniżej).
tło
Dla mnie to pytanie powstało naturalnie podczas analizowania odpowiedzi Lucy Tevisan na pytanie Czy środowiska wykonawcze dla P wymagają zasobów EXP do przekroczenia górnej granicy? … Czy znane są konkretne przykłady?
Pytanie dotyczy także pytania MathOverflow: Jakie są najbardziej atrakcyjne problemy matematyczne Turinga? , w odmianie, w której słowo „matematyka” zostało zmienione na „inżynieria”, w uznaniu, że oszacowanie czasu działania jest wszechobecnym problemem inżynieryjnym związanym (na przykład) z teorią sterowania i projektowaniem obwodu.
Zatem ogólnym celem przy zadawaniu tego pytania jest uzyskanie lepszego zrozumienia / intuicji odnośnie tego, które praktyczne aspekty estymacji środowiska wykonawczego w klasie złożoności P są wykonalne (to znaczy wymagają zasobów obliczeniowych w P do oszacowania), w porównaniu z niemożliwym (tj. wymagają zasobów obliczeniowych w EXP do oszacowania), a formalnie nierozstrzygalne.
--- edycja (po odpowiedzi) ---
Dodałem twierdzenie Violi do wiki społeczności MathOverflow „Atrakcyjne problemy Turinga - nierozstrzygalne”. Jest to pierwszy wkład wiki związany z klasą złożoności P; świadczy to o nowości, naturalności i szerokim zakresie twierdzenia Violi (i IMHO także o jego pięknie).
--- edycja (po odpowiedzi) ---
Monografia Jurisa Hartmanisa Wykonalne obliczenia i możliwe do udowodnienia właściwości złożoności (1978) obejmują wiele tego samego materiału, co dowód Emanuele Violi.
źródło
Odpowiedzi:
Problem jest nierozstrzygalny. W szczególności możesz zredukować problem zatrzymania do niego w następujący sposób. Biorąc pod uwagę wystąpienie problemu zatrzymania , skonstruuj nową maszynę która działa w następujący sposób: na wejściach o długości symuluje na dla kroków. Jeśli akceptuje, zapętlaj dla kroków i zatrzymaj; w przeciwnym razie wykonaj pętlę dla kroków i zatrzymaj.M ′ n M x(M,x) M′ n M x n M n2 n3
Jeśli zatrzymuje się na , robi to w krokach , więc czas działania wynosiłby . Jeśli nigdy się nie zatrzymuje, czas działania wynosi co najmniej .M x t=O(1) M′ O(n2) M M′ n3
Dlatego możesz zdecydować, czy akceptuje , decydując, czy czas działania wynosi czy .M x M′ O(n2) O(n3)
źródło
To jest przeformułowanie odpowiedzi Emanuele Violi, aby być bardziej zrozumiałym.
Pokażemy, że dany problem jest nierozstrzygalny zmniejszenie ogólnego problemu stopu do niego.P H
Niech będzie dowolnym przykładem problemu zatrzymania, to znaczy musimy zdecydować, czy ( zatrzymuje się na ). Zbuduj maszynę Turinga która działa w następujący sposób:(M,x) M(x)↓ M x M∗
Teraz obserwujemy następujące implikacje:
i
Dlatego . Zakładając, że było algorytmicznie rozstrzygalne, podobnie jak , co daje sprzeczność.H(M,x)⇔P(M∗,2) P H □
źródło
Pozytywną stroną jest rozstrzygnięcie, czy maszyna Turinga z jedną taśmą działa w czasie dla danego , patrz:n↦C⋅n+D C,D∈N
źródło
Problem został również rozwiązany w moim artykule „ Intensywna treść twierdzenia Rice'a ” POPL'2008, w którym udowadniam, że żadna „klika złożoności” nie jest rozstrzygalna. Klika złożoności to klasa programów zamkniętych programów wrt o podobnym zachowaniu i złożoności. Zapewniam także niezbędne warunki dla właściwości orzekających częściowo.
Programy działające w O (n ^ k) są klikami złożoności w powyższym sensie, stąd zbiór nie jest rozstrzygalny.
Wynik został niedawno rozszerzony na ustawienia subrekursywne (takie jak P) autorstwa Mathieu Hoyrupa: decydujące właściwości funkcji subrekursywnych (ICALP 2016).
źródło
Aby dodać do poprzednich odpowiedzi, ten problem jest nie tylko nierozstrzygalny, ale zakończony. Dlatego jest nierozstrzygalne, nawet jeśli decydent ma wyrocznię dla problemu zatrzymania.Σ02
Aby wyjaśnić kompletność, podczas gdy warunek przyrzeczenia czasu P jest również -kompletny, istnieje rozstrzygalny zestaw kodów tak że wszystkie maszyny w są czasem wielomianowym, a pytanie brzmi wykonać na . SSO( n 2 ) Σ 0 2 S.Σ02 S S O(n2) Σ02 S
Aby to udowodnić, wybierz complete , z obliczanym czasem wielomianowym (dla liczb binarnych). φ φ (x)⇔ ∃ k ∀ mΣ02 φ ψφ(x)⇔∃k∀mψ(x,k,m) ψ
Następnie utrzymuje iff następująca maszyna to gdzie jest długością wejściową (maszyna dba tylko o długość wejściową):O ( n 2 ) nφ(x) O(n2) n
dla w 0 do : jeśli : # testowane przy użyciu zatrzymania pętli poczekaj na kroki zatrzymanian ∀ m < nk n ∀m<nψ(x,k,m)
n2
n 2
Zauważ, że dla każdego niezbyt małego , czy program zawsze zatrzymuje się (na przykład) w jest , ale solidne pytanie o granice daje -kompletność.≤ n 2 + c Π 0 1 Σ 0 2c ≤n2+c Π01 Σ02
źródło
oto najnowsze, bardziej systematyczne analizy / kąty / wyniki dotyczące tego pytania i powiązanych, wprowadzające pojęcie „weryfikowalności algorytmicznej” i analog podobny do ryżu dla teorii złożoności. jedna z odpowiednich sekcji streszczenia jest następująca i istnieje wiele innych powiązanych twierdzeń związanych z udowodnieniem P vs NP itp
Dlaczego pojęcie złożoności obliczeniowej jest trudne dla weryfikowalnej matematyki / Hromkovica
źródło
Rozwiązanie Violi można uogólnić na dowolny czas pracy (poza poli): Możesz zmniejszyć problem zatrzymania do niego w następujący sposób. Biorąc pod uwagę wystąpienie problemu zatrzymania (M, x), zbuduj nową maszynę M ', która działa w następujący sposób: na wejściach o długości n symuluje M na x dla kroków f (n) lub do momentu zatrzymania M, gdzie f (n ) to dowolna dowolna funkcja rosnąca (większa niż stała) n. (Obs .: M ′ odczytuje stopniowo dane wejściowe, aby uniknąć marnowania czasu liniowego [O (n)] tylko na niepotrzebne odczytywanie wszystkich danych wejściowych, jeśli jest wystarczająco duży, a M zatrzymuje się.)
Jeśli M zatrzymuje się na x, robi to w krokach T = O (1), więc czas działania M 'wynosiłby O (1). Jeśli M nigdy się nie zatrzymuje, czas działania M 'wynosi O (n ^ 2 * f (n)).
Dlatego możesz zdecydować, czy M akceptuje x, decydując, czy czas działania M 'wynosi O (1) czy O (n ^ 2 * f (n)).
Następnie kod pomocniczy z Rafaela można odpowiednio uogólnić poprzez:
Niech (M, x) będzie dowolnym wystąpieniem problemu zatrzymania, to znaczy musimy zdecydować, czy M zatrzyma się na x. Zbuduj deterministyczną maszynę Turinga (DTM) M *, która działa w następujący sposób:
Teraz obserwujemy następujące implikacje:
M zatrzymuje się na x po co najwyżej k (stałych) krokach => T (M *) = O (1) i
M nigdy nie zatrzymuje się na x => T (M *) = O (n ^ 2 * f (n))
Dlatego nawet podjęcie decyzji, czy czas działania dowolnego DTM jest po prostu większy niż stały, jest tak trudne, jak problem zatrzymania. □
źródło