Czy nierozstrzygalne atrybuty P stanowią przeszkodę w podejmowaniu decyzji o P w porównaniu z NP? (odpowiedź: może)

Zadaje się pięć powiązanych pytań i oczekuje się jednej zintegrowanej odpowiedzi:

• P1: Czy istnieją języki które są rozpoznawane wyłącznie przez maszyny Turinga w  których wykładników czasu wykonywania nie można rozstrzygnąć ?$L$$P$
• Q2: Czy przykłady tych maszyn Turinga mogą być skończone?
• P3: Czy te maszyny Turinga mogą być konkretnie tworzone? ( np. przez wyrocznie, które „zgadują” je, a nie skończą je konstruować).
• P4: Jakie inne atrybuty P (oprócz wykładników czasu wykonywania) są obecnie znane jako nierozstrzygalne? Dla jakich atrybutów pytanie to jest otwarte?$P$
• P5: Czy nierozstrzygalne atrybuty stanowią przeszkodę dla rozstrzygalności ?P ≠ N P$P$$P \ne NP$

Zwróć uwagę na słowo „wyłącznie” w pierwszym kwartale (co wyklucza sugerowaną odpowiedź Lance'a Fortnowa).

Wnioski i konwersja na Wiki Wiki

• Pytanie, które brzmi: „Czy nierozstrzygalne atrybuty P stanowią przeszkodę w podjęciu decyzji o P w porównaniu z NP?”, Jest otwarte i uważa się je za trudne, podobnie jak wiele szczegółowych pytań (takich jak Q1–4 powyżej), które są z nim naturalnie związane.

• Monografia Jurisa Hartmanisa z 1978 r. Feasible Computations and Provable Complexity Properties stanowi dobry wstęp do literatury i (najwyraźniej) nie opublikowano żadnej recenzji od czasu Hartmanisa.

• Ta klasa pytań jest wystarczająco niezbadana, że ​​wyzwanie znalezienia rygorystycznych dowodów jest ściśle zmieszane z wyzwaniem wyboru dobrych definicji początkowych.

• Przemyślane uwagi i wnikliwe szkice dowodowe dostarczone przez Travis Service i Alex ten Brink są doceniane i doceniane.

Ponieważ pytanie jest otwarte i ponieważ jest omawiane w wielu wątkach matematycznych blogów ( 1 , 2 , 3 , 4 , 5 , 6 ), pytanie to zostało oflagowane do konwersji na Community Wiki.

Aktualizacja II i Podsumowanie

Uświadomiłem sobie, że monografię Jurisa Harmanisa z 1978 r. Wykonalne obliczenia i możliwe do udowodnienia właściwości złożoności można odczytać jako dogłębną odpowiedź na pytania 1–5 . Ponadto (doskonałe) szkice próbne Q1 i Q4 przedstawione poniżej przez Travis Service i Alexa Ten Brink stanowią nowoczesne potwierdzenie i rozszerzenie ogólnych wniosków Hartmanisa, że:

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

Dlatego powinniśmy oczekiwać, że wyniki dotyczące optymalności wszystkich programów wykonujących tę samą funkcję co dany program będą się różnić od wyników optymalizacyjnych dla wszystkich programów, które można formalnie udowodnić, że są równoważne z danym programem. ...

Powinniśmy [rozważyć] możliwość, że ten słynny problem [ ] może nie być rozwiązany w sformalizowanej teorii matematycznej, takiej jak teoria mnogości.$P\overset{?}{=}NP$

Z monografii Hartmanisa i odpowiedzi udzielonych przez Travisa i Alexa wynika, że Q1–5 znacznie wykraczają poza obecny stan wiedzy w zakresie teorii złożoności. Co więcej, te pytania / odpowiedzi najwyraźniej są na tyle subtelne, że wymagają dokładnych korekt definicyjnych i uzasadniają ekspozycje o długości monografii… które, mam nadzieję, nie zniechęcają ludzi do zamieszczania dalszych odpowiedzi. :)

Dalszą dyskusję techniczną można znaleźć w odpowiedzi Joela Davida Hamkinsa na MathOverflow na pytanie Czy problem może być jednocześnie czasem wielomianowym i nierozstrzygalny? (zalecane przez Alex ten Brink).

Jeśli w monografii Hartmanisa zastąpiono „obliczenie funkcji” wyrażeniem „symulacja dynamiki”, wynik można odczytać jako traktat o teoretycznych ograniczeniach złożoności inżynierii systemów… jest to praktyczny powód, dla którego my inżynierowie dbamy o te problemy.

Oded Goldreich wyraził ostatnio przeciwną opinię do Hartmanisa w liście do redaktora CACM zatytułowanym „O złożoności obliczeniowej” :

Niestety, obecnie brakuje dobrych teoretycznych odpowiedzi na najbardziej naturalne pytania dotyczące wydajnego obliczania. Nie dzieje się tak dlatego, że zadajemy niewłaściwe pytania, ale dlatego, że pytania te są bardzo trudne.

Jest (oczywiście) całkowicie możliwe do wyobrażenia, że ​​zarówno opinie Hartmanisa, jak i Goldreicha okażą się słuszne, na przykład formalny dowód nierozstrzygalności rozdzielalności PvsNP można zasadnie uznać za potwierdzający oba punkty widzenia.

Aktualizacja I

Przemyślane komentarze (poniżej) Travisa Service i Alexa Ten Brinka sugerują (w efekcie), że w pierwszym kwartale wyrażenie „nierozstrzygalne” nie jest synonimem „nierozpoznawalnego” i że odpowiedzi na pytania 2–5 mogą zależeć od tego rozróżnienia. Nie jest dla mnie wcale jasne, który definitywny wybór doprowadziłby do najsilniejszych twierdzeń, a także najlepiej uchwycił naszą intuicję klasy P. Odpowiedzi i komentarze dotyczące tego pytania są mile widziane.

Przypomina się uwaga Felixa Kleina w jego elementarnej matematyce z zaawansowanego punktu widzenia: geometria (1939):

Innym przykładem koncepcji, która pojawia się z mniej lub bardziej precyzyjną naiwną percepcją przestrzeni, którą musimy dodać jako uzupełnienie naszego systemu geometrii, jest pojęcie (arbitralnej) krzywej . Każda osoba uważa, że ​​wie, czym jest krzywa, dopóki nie nauczy się tyle matematyki, że niezliczone możliwe nieprawidłowości mylą ją.

Podobnie jak w przypadku krzywych, tak też w przypadku języków akceptowanych przez maszyny Turinga w  … co kiedyś wydawało mi się (najprostsze i najbardziej naturalne ze wszystkich klas złożoności) teraz myli mnie (niezliczoną?) Niemożliwą do zweryfikowania i / lub nierozstrzygalną cechą jego członków . Szeroką motywacją w pytaniu 1–5 było znalezienie drogi przez ten zagmatwany gąszcz, ale dotychczasowe odpowiedzi (Travis Service i Alex ten Brink) dostarczyły dalszych powodów do zamieszania!$P$

Pokolenie matematyków Kleina ciężko pracowało nad znalezieniem dobrych definicji krzywych i innych podstawowych elementów teorii mnogości, geometrii i analizy. Przegląd na poziomie podstawowym można znaleźć w dyskusji na temat Alexandra Rogatej Sfery w Wikipedii

      
      Osadzenie kuli w R3

W XX wieku analiza „dzikich rozmaitości”, takich jak sfera Aleksandra, pomogła wyjaśnić różnice między topologicznymi rozmaitościami, fragmentarycznie ciągłymi rozmaitościami i różnorodnymi rozmaitościami. Podobnie w XXI wieku być może udoskonalenia definicji związanych z pomogą oswoić dzikie języki P i dzikie maszyny Turinga… chociaż określenie odpowiednich udoskonaleń nie będzie łatwym zadaniem.$P$$P$

tło

Te powiązane pytania wynikają z pytań wiki społeczności MathOverflow „ Jakie są najbardziej atrakcyjne nierozwiązywalne problemy Turinga w matematyce? ” I „ Jakie pojęcia są stosowane, ale nie są jasno zdefiniowane we współczesnej matematyce? ” W szczególności Colin Tan poprosił o postawienie pytania zadanego powyżej opublikowane jako osobne pytanie.

Aby zapoznać się z zapleczem technicznym, zobacz pytanie TCS StackExchange „ Czy granice czasu wykonywania w P są rozstrzygalne? ”, W szczególności zwięzły dowód Emanuele Violi, że odpowiedź brzmi „nie”. Należy również zauważyć, że podobne wyniki udowodnił Juris Hartmanis w swojej monografii Wykonalne obliczenia i możliwe do udowodnienia właściwości złożoności (1978).

W tym tygodniu na blogu Lance Fortnow / Bill GASARCH Złożoność obliczeniowa jest gospodarzem ich sondażu „ Czy czy nie?$P=NP$ ” - piąte i ostatnie zadane pytanie zachęca do komentowania pytania Fortnow / GASARCH.

Na pytanie 1 odpowiedź brzmi „nie”. Niech jest językiem w P, a M niech będzie dowolnym wielomianowym urządzeniem Turinga rozpoznającym L (którego czas działania przyjmuje się za nierozstrzygalny). Dla każdego k ∈ N niech M k będzie maszyną Turinga, która na wejściu x długości n pierwszych pętli dla n k kroków następnie uruchamia M na x dla n k + k kroków i akceptuje, jeśli M akceptuje x (w obrębie tych n k + $L$$P$$M$$L$$k \in \mathbb{N}$$M_k$$x$$n$$n^k$$M$$x$$n^k + k$$M$$x$$n^k + k$kroki) i odrzuca inaczej. Czas działania wynosi Θ ( n k ) dla każdego k .$M_k$$\Theta(n^k)$$k$

Ponieważ przebiega w czasie wielomianowym, istnieje pewne k ′ ∈ N, takie że M działa w O ( n k ′ ) (nawet jeśli nie wiemy, co to jest k ′ ), a zatem dla wszystkich k wystarczająco dużych M k rozpoznaje L i ma rozsądny czas działania.$M$$k' \in \mathbb{N}$$M$$O(n^{k'})$$k'$$k$$M_k$$L$

EDYTOWAĆ

Myślę, że następująca odpowiedź jest bardziej zgodna z zamierzeniami oryginalnego plakatu z pytaniem 1.

Twierdzenie: Istnieje język taki, że jeśli N jest dowolną maszyną Turinga, która decyduje o L, wówczas spełniony jest przynajmniej jeden z poniższych warunków:$L \in P$$N$$L$

1) Nie ma dowodu, że akceptuje L lub$N$$L$

2) Nie ma dowodu, że zatrzymuje się w krokach f ( n ) (dla dowolnej funkcji f ( n ) ).$N$$f(n)$$f(n)$

Dowód Szkic: Niech będzie Maszyna Turinga, który nie zatrzymuje się na pustej taśmy i dla których nie istnieje dowód, że M nie zatrzymuje się na pustej taśmie (wyniki niepodległość w Informatyki przez Hartmanis i Hopcroft pokazy takiej M puszkę skutecznie znaleźć).$M$$M$$M$

Niech .$L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$

Ponieważ nie zatrzymuje się, L jest w rzeczywistości pustym językiem, ale nie ma na to dowodów (ponieważ to by dowodziło, że M się nie zatrzymuje).$M$$L$$M$

Niech będzie dowolną maszyną Turinga. Jeśli istnieje zarówno dowód, że N decyduje L, jak i dowód, że N działa w krokach f ( n ), wówczas wykonanie N podczas uruchomienia na wejściu 1 zapewnia albo dowód, że M zatrzymuje się (tj. Jeśli N akceptuje) lub że M robi nie zatrzymuj się (tzn. jeśli N odrzuci). Zatem jeśli N w sposób decydujący decyduje o L, czas działania N nie jest rozstrzygalny i odwrotnie.$N$$N$$L$$N$$f(n)$$N$$1$$M$$N$$M$$N$$N$$L$$N$

$n^{i+1}$$n^i$$i$$\neq$

Po zastanowieniu się bardziej na ten temat, wydaje mi się, że znalazłem (możliwą) odpowiedź na twoje czwarte pytanie .

• P4: Jakie inne atrybuty P (oprócz wykładników czasu wykonywania) są obecnie znane jako nierozstrzygalne? Dla jakich atrybutów$P$$P$

Udowodniłem odmianę twierdzenia Rice'a, która odpowiada na twoje pytanie dla większości właściwości. Tym razem postaram się wyjaśnić (odpowiedź Travis Service była o wiele jaśniejsza i bardziej ogólna niż moja poprzednia odpowiedź).

$E$$E$$O(f(n))$$f(n)=\Omega(n \log n)$$f(n)=\Omega(g(n))$$g(n)$

$f(n)$$P$

$S$$S$$S$$S \subseteq R$$S$

$P$$S \subseteq P$

$S$

$P(E)$$E$$P$$E$$S$$E$$(A, i)$$A$$i$$A$$A$$i$

$S$$s \in S$$S$$C$$s$$C$$g(n)$

function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

$O(n \log n)$

$P(H)$$A$$i$$A$$i$$t$$H$$X$$|X| \geq t$$H$$S$$P(H)$

$A$$i$$C$$s \in S$$P(H)$$P(H)$

Mogę odpowiedzieć na twoje Q1 przecząco, a tym samym odpowiedzieć na Q2 i Q3 przecząco. Nie jestem jednak pewien co do Q4 lub Q5 .

• $L$$P$

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

$T$$k$$T$$O(n^k)$$M$$k$$T$$T$$k$ $T$

$L$$P$$T$$O(n^k)$$k$$L$$M$$k$$T$

$L$$P$$T$$L$$T$

$L$$P$$M$$T$$L$$T$$L$

$L$$P$$L$$O(n^k)$$M$$n$$n^{k+1}$$n^{k+2}$$L$

$M$$P$$L$$L$$k$$M$

Ten rodzaj myślenia o nierozstrzygalności jest najwyraźniej dość powszechny, pamiętam post (blog?) Na bardzo podobny temat: pytanie brzmiało: „czy można rozstrzygnąć, czy Pi ma„ ostatnie zero ”, więc czy Pi przestaje mieć zera w swoich zerach? dziesiętna reprezentacja, jeśli zejdziesz wystarczająco daleko w dół tej reprezentacji. Obecnie nie wiemy, czy tak jest. Możemy nawet nie być w stanie tego udowodnić, a nawet być niezależni od naszych systemów aksjomatów (a tym samym nie do udowodnienia). Ponieważ jednak odpowiedź brzmi „prawda” lub „fałsz”, TM zwracająca wartość true i TM zwracająca wartość false decydują o tym przypadku, a zatem problem można rozstrzygać.

Zobaczę, czy mogę gdzieś znaleźć ten post w Internecie.

Edytować:

Znalazłem to na Mathoverflow .