Czy granice czasu wykonywania w P są rozstrzygalne? (odpowiedź: nie)

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 ) $k$$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.

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 $(M,x)$$M'$$n$$M$$x$$n$$M$$n^2$$n^3$

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(n^2)$$M$$M'$$n^3$

Dlatego możesz zdecydować, czy akceptuje , decydując, czy czas działania wynosi czy .$M$$x$$M'$$O(n^2)$$O(n^3)$

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)\downarrow$$M$$x$$M^*$

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Teraz obserwujemy następujące implikacje:

$\begin{align*} M(x) \downarrow \quad &\Rightarrow \exists n_0 \in \mathbb{N} : M \text{ halts on } x \text{ after at most } n_0 \text{ steps} \\ &\Rightarrow \forall y : n \geq n_0 \Rightarrow M^*(y) \text{ executes } n^2 \text{ arbitrary steps} \\ &\Rightarrow T_{M^*}(n) \in \mathcal{O}(n^2) \end{align*}$

i

$\begin{align*} M(x) \uparrow \quad &\Rightarrow \forall n \in \mathbb{N} : M \text{ does not halt on } x \text{ in less than } n \text{ steps} \\ &\Rightarrow \forall y : M^*(y) \text{ executes } n^3 \text{ arbitrary steps} \\ &\Rightarrow T_{M^*}(n) \in \Omega(n^3) \end{align*}$

Dlatego . Zakładając, że było algorytmicznie rozstrzygalne, podobnie jak , co daje sprzeczność. $H(M,x) \Leftrightarrow P(M^*,2)$$P$$H$$\square$

Pozytywną stroną jest rozstrzygnięcie, czy maszyna Turinga z jedną taśmą działa w czasie dla danego , patrz:$n \mapsto C \cdot n + D$$C, D \in \mathbb{N}$

David Gajser: Sprawdzanie, czy niedeterministyczne maszyny Turinga z jedną taśmą działają w czasie$Cn+D$ , arXiv: 1312.0496

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

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. $Σ^0_2$

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$Σ^0_2$$S$$S$$O(n^2)$$Σ^0_2$$S$

Aby to udowodnić, wybierz complete , z obliczanym czasem wielomianowym (dla liczb binarnych). φ φ (x)⇔ ∃ k ∀$Σ^0_2$$φ$$φ(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 ) $φ(x)$$O(n^2)$$n$

dla w 0 do :     jeśli : # testowane przy użyciu         zatrzymania pętli     poczekaj na kroki zatrzymanian ∀ m < $k$$n$
n $∀m<n \, ψ(x,k,m)$

$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 $c$$≤n^2+c$$Π^0_1$$Σ^0_2$

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

  Po pierwsze, dowodzimy twierdzenia Rice'a o niewiarygodności, twierdząc, że każdy nietrywialny problem semantyczny dotyczący programów nie jest prawie wszędzie możliwy do rozwiązania w matematycznie weryfikowalnej algorytmie „AV”. Korzystając z tego, pokazujemy, że istnieje nieskończenie wiele algorytmów (programów, które są algorytmami możliwymi do udowodnienia), dla których nie istnieją dowody, że działają one w czasie wielomianowym lub że nie działają w czasie wielomianowym. ...

  Zauważ, że jeśli P! = NP jest możliwe do udowodnienia w matematyce AV, to dla każdego algorytmu A można udowodnić, że „A nie rozwiązuje ZADOWOLENIA lub A nie działa w czasie wielomianowym”. Co ciekawe, w końcu pokazujemy, że istnieją algorytmy, dla których nie można udowodnić, że nie działają one w czasie wielomianowym, ani że nie rozwiązują ZADOWOLENIA. Ponadto istnieje algorytm rozwiązujący ZADOWOLENIE, dla którego nie można udowodnić w matematyce AV, że nie działa on w czasie wielomianowym.

  Ponadto pokazujemy, że P = NP implikuje istnienie algorytmów X, dla których twierdzenie „X rozwiązuje ZADOWOLENIE w czasie wielomianowym” nie jest możliwe do udowodnienia w matematyce AV.

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:

1. M * (wejście) = {
2. n: = 0
3. Przeczytaj pierwszy symbol z wejścia
4. Pętla:
5. n: = n + 1
6. Symuluj M (x) dla kroków f (n) lub do momentu zatrzymania M (x)
7. Przeczytaj następny symbol z wejścia
8. Pętla, aż do końca_wejścia lub do momentu zatrzymania M (x)
9. }

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