NP-kompletne warianty nierozwiązywalnych problemów?

Przykłady ograniczone -Complete wariantów nierozstrzygalnych zestawach:$NP$

Ograniczony problem zatrzymania = { | Maszyna NTM M zatrzymuje się i przyjmuje x w ciągu t kroków}$(M, x, 1^t)$$M$$x$$t$

Ograniczone płytki = { | jest płytki kwadratu o powierzchni t 2 za pomocą płytek z T }$(T, 1^t)$$t^2$$T$

Problem ograniczonej korespondencji pocztowej = { | istnieje pasujący zestaw domino, który używa co najwyżej k domino z zestawu domino T (w tym domino powtarzane)}$(T, 1^t)$$k$$T$

Czy zawsze jest możliwe uzyskanie wariantu dla każdego problemu nierozstrzygalnego poprzez nałożenie pewnych ograniczeń na obliczenia? Czy istnieją inne naturalne przykłady tego rodzaju?$NP$

Jak zauważył Jukka, odpowiedź brzmi trywialnie nie na wszystkie nierozstrzygalne problemy.

Bardziej rozsądne pytanie brzmiałoby: czy każdy problem, który jest kompletny dla klasy języków z rekurencyjnie wymiennymi, może zostać uzupełniony NP w prosty sposób? Nie jestem pewien, czy jest to ogólnie prawdą, ale w szczególnych przypadkach, o których wspominasz w swoim pytaniu (Ograniczanie i kafelkowanie) problemy te są kompletne dla RE nawet przy „specjalnych” wielomianowych skróceniach czasu. (W tej odpowiedzi pozostawiam „specjalne”, w większości niezdefiniowane, ale potrzebne właściwości można z niego opracować).

Więc jeśli zadamy jeszcze bardziej rozsądne pytanie: czy każdy problem, który jest kompletny (w ramach specjalnych redukcji czasu przestoju) dla klasy języków z rekurencyjnie wymiennymi, może zostać uzupełniony NP w prosty sposób? , tutaj odpowiedź brzmi tak . Ponosi żadnej RE uzupełniania problemu , zdefiniowanym w odniesieniu do maszyny Turingowi M A , które ma parę wejść ( x , y ) , takie, że x ∈ $A$$M_A$$(x,y)$ . Zakładamy, że istnieje wielomian skrócenie czasu od powstrzymania problem do A . Zdefiniuj „Bounded-A”, aby był zbiorem par ( x , 1 t ) tak, że y ma długość co najwyżej t, tak że M A ( x , y ) zatrzymuje się w ciągu t kroków.$x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$$A$$(x,1^t)$$y$$t$$M_A(x,y)$$t$

Wyraźnie "ograniczony-A" jest . Jest to także N P -Complete ponieważ możemy zmniejszyć N P -Complete ograniczone do powstrzymania problem ograniczony-A w czasie wielomianowym (zauważ, że tutaj potrzebne są specjalne właściwości na wielomianu skrócenie czasu badania , aby upewnić się, że przenosi się do powstrzymania jak ograniczone- cóż: tzn. musisz być w stanie efektywnie obliczyć górną granicę t ′ na jak długo ma działać M A ( R ( M , x ) , y ) , zakładając, że M ( x ) zatrzymuje się w ciągu$NP$$NP$$NP$$R$$t'$$M_A(R(M,x),y)$$M(x)$ kroków.)$t$

$NP$

$\aleph_0$

Wydaje mi się, że dla każdego problemu w tym samym stopniu nierozwiązywalności istnieje pewien rodzaj ograniczenia zasobów (czasu), który daje język NP-zupełny.

Uwaga: Może powinienem być bardziej konserwatywny, mówiąc „dla każdego problemu w tym samym stopniu nierozwiązywalności”. Może się zdarzyć, że powyższe stwierdzenie jest prawdziwe tylko dla klasy problemów o takim samym stopniu, jak powiedzmy problem HALTING.

Zobacz także: Martin Davis, What Is ... Turing Reducibility ?, Notices of AMS, 53 (10), s. 1218--1219, 2006.