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

64

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 ) nkMM O(nk)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.

John Sidles
źródło
W odpowiedzi na pytania zadane na blogu Lance'a Fortnowa i Billa GASARCHA pod tytułem „75 lat informatyki”, rozpoczynając od „Często żałowałem, że Turing trzeźwo nie zapytał:„ Jakie są możliwe do zweryfikowania procesy, które można przeprowadzić przy obliczaniu liczba? ”... zamiast Turinga zadawać fatalnie trudniejsze pytanie:„ Jakie są możliwe procesy, które można przeprowadzić przy obliczaniu liczby? ”, następne pytanie będzie (w przybliżeniu)„ Czy istnieją maszyny Turinga, które można udowodnić w NP, którego członkostwo w P jest nierozstrzygalne? ”To ma pokazać, że wciąż o tym myślę! :)
John Sidles
2
Chociaż dowód I Emanuele Violi jest jaśniejszy, na Mathoverflow zadano bardzo podobne pytanie: mathoverflow.net/questions/28056/…
Alex ten Brink
Kilka odpowiedzi i pomysłów w tym wątku okazało się trafnych w eseju / zestawie pytań, które Dick Lipton opublikował na swoim blogu Lost List Godela ; zestaw esejów / pytań brzmi „Pierwsze na podstawie P = NP”. URL: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp
John Sidles
Chociaż granice w P są nierozstrzygalne, nie powstrzymuje to nikogo przed próbowaniem (przez dalsze ograniczanie się). Przykład podany w tej odpowiedzi na pytanie
Artem Kaznatcheev
1
To pytanie zainspirowało następujący artykuł: arxiv.org/abs/1307.3648
David G

Odpowiedzi:

83

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

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 .Mxt=O(1)MO(n2)MMn3

Dlatego możesz zdecydować, czy akceptuje , decydując, czy czas działania wynosi czy .MxMO(n2)O(n3)

Manu
źródło
4
dlaczego M musi zatrzymać się na x (jeśli tak jest) w krokach O (1)?
Suresh Venkat
10
M i są ustalone niezależnie od . xn
Manu
2
Bardzo sprytny dowód, czy jest to odmiana dobrze znanego wyniku, czy właśnie go opracowałeś?
Antonio E. Porreca,
3
@Raphael: To drażliwy obszar, który, jak sądzę, nie rozwiązaliśmy. Niektóre witryny wymiany stosów zachęcają do edytowania odpowiedzi innych. Nie mamy takiej polityki, ale praktycznie nie widziałem, żeby to zrobiono. Jedna kwestia techniczna: jeśli odpowiedź jest edytowana za dużo, staje się społecznością wiki, a @Emanuele nie uzyskałby żadnych dalszych punktów powtórzeń, gdyby jego odpowiedź została później oceniona. Myślę, że dodatkowe wyjaśnienie pomogłoby wyjaśnić: John Sidles początkowo myślał, że obietnica nie została wykorzystana, ale dowód używa silniejszej obietnicy: działa w lub , nie tylko P.Mn2n3
Aaron Sterling
2
@John: Dopóki nie podano opublikowanych odniesień, rozważ tę wytyczną .
Raphael
29

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

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

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:

M(x)n0N:M halts on x after at most n0 stepsy:nn0M(y) executes n2 arbitrary stepsTM(n)O(n2)

i

M(x)nN:M does not halt on x in less than n stepsy:M(y) executes n3 arbitrary stepsTM(n)Ω(n3)

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

Raphael
źródło
12

Pozytywną stroną jest rozstrzygnięcie, czy maszyna Turinga z jedną taśmą działa w czasie dla danego , patrz:nCn+DC,DN

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

Andrej Bauer
źródło
1
Nie brakuje niezwykłego zachowania dzięki niewielkim jednostkom TM z jedną taśmą. :)
Kaveh
4

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

Andrea Asperti
źródło
2

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. Σ20

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.Σ20SSO(n2)Σ20S

Aby to udowodnić, wybierz complete , z obliczanym czasem wielomianowym (dla liczb binarnych). φ φ (x) k mΣ20φψφ(x)kmψ(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 < nkn
n 2m<nψ(x,k,m)

n2

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 2cn2+cΠ10Σ20

Dmytro Taranovsky
źródło
-1

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.

vzn
źródło
-3

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

André Luiz Barbosa
źródło
2
1) Proszę użyć LaTeX. 2) Jaki jest nowy wkład w to pytanie? 3) Twoje rozumowanie jest błędne. Symulacja wymaga czasu , aby pewnością nie mógł działać w stałym czasie. O ( n ) M MO(n)M
Raphael
W przypadku wystarczająco dużego n, jeśli M (x) zatrzymuje się, wówczas również jego symulacja zatrzymuje się i wraca do M * w obrębie n0 (stałych) kroków.
André Luiz Barbosa