Problem decyzyjny, o którym nie wiadomo, że występuje w PH, ale będzie w P, jeśli P = NP

Edycja : Jak Ravi Boppana słusznie wskazał w swojej odpowiedzi, a Scott Aaronson dodał również inny przykład w swojej odpowiedzi , odpowiedź na to pytanie okazała się „tak” w sposób, którego w ogóle się nie spodziewałam. Najpierw pomyślałem, że nie odpowiedzieli na pytanie, które chciałem zadać, ale po pewnym zastanowieniu konstrukcje te odpowiadają przynajmniej na jedno z pytań, które chciałem zadać, to znaczy: „Czy jest jakiś sposób na udowodnienie wyniku warunkowego” P = NP ⇒ L ∈P 'bez udowodnienia bezwarunkowego wyniku L ∈PH? ”Dzięki, Ravi i Scott!

Czy istnieje problem decyzyjny L taki, że oba poniższe warunki są spełnione?

L nie jest znane z hierarchii wielomianowej.
Wiadomo, że P = NP implikuje L ∈P.

Sztuczny przykład jest tak dobry jak naturalny. Ponadto, chociaż używam litery „ L ”, może to być problem obietnicy zamiast języka, jeśli to pomoże.

Tło . Jeśli wiemy, że problem decyzyjny L leży w hierarchii wielomianowej, to wiemy, że „P = NP ⇒ L ∈P”. Zadaniem pytania jest pytanie, czy zachodzi odwrotność. Jeśli istnieje język L spełniający powyższe dwa warunki, można go uznać za dowód na to, że konwersja kończy się niepowodzeniem.

Pytanie zostało uzasadnione interesującym komentarzem Joe Fitzsimonsa do mojej odpowiedzi na pytanie Waltera Bishopa „ Konsekwencje #P = FP ”.

cc.complexity-theory conditional-results np polynomial-hierarchy Tsuyoshi Ito
źródło

Udowodnienie uniwersalnego negatywu jest zawsze trudne (er), ale byłbym zaskoczony, gdyby taki język istniał. Uogólniona hipoteza Linial-Nisan (gdyby okazała się prawdziwa) nie sugerowałaby, o co pytasz, nie wierzę. Oznaczałoby to po prostu, że BQP nie było zawarte w PH. Gdyby PH spadło do P, BQP nadal nie byłby zawarty w P (H).

Daniel Apon

Czy pytasz, czy istnieje klasa złożoności X st X nie jest podzbiorem PH, a P = NP -> X = P?

Philip White,

@Filip: Tak, ale nie sądzę, że to zmienia problem, ponieważ zwykle możemy przekonwertować problem decyzyjny L na X problemów decyzyjnych klasy X, które można zredukować do L. Przynajmniej taki był mój zamiar zadać to pytanie pod względem problemów decyzyjnych .

Tsuyoshi Ito,

Może chcesz wymagać, aby język był jakoś zbliżony do PH, oprócz twoich obecnych wymagań? Może, powiedzmy, w PSPACE (choć można argumentować, jak blisko PSPACE jest do PH; patrz S. Fenner, S. Homer, M. Schaefer, R. Pruim. Hierarchie hiper-wielomianowe i skok wielomianowy. Teoretyczna informatyka. Tom 262 ( 2001), s. 241–256 cse.sc.edu/~fenner/papers/hyp.pdf ). A może naprawdę chcesz poprosić o naturalny taki język.

L

$L$

Joshua Grochow

@Joshua: Dziękuję za komentarz i odniesienie. Jak stwierdzono w aktualizacji (wersja 3), teraz myślę, że zadałem właściwe pytanie (w przeciwieństwie do tego, co dodałem w wersji 2). Chciałem wiedzieć „Czy jest jakiś sposób na udowodnienie wyniku warunkowego„ P = NP ⇒ L∈P ”bez udowodnienia bezwarunkowego wyniku L∈PH?”. W tym celu naturalność problemu nie powinna być wymagana, ponieważ raz jest metodą sprawdzającą, powinna mieć zastosowanie zarówno do przykładów naturalnych, jak i wymyślonych.

Tsuyoshi Ito,

Odpowiedzi:

Ponieważ nie przeszkadza ci sztuczny język, co powiesz na zdefiniowanie jako pustego, jeśli P jest równe NP, i jako problemu zatrzymania, jeśli P nie jest równe NP. Okej, to trochę oszustwo, ale myślę, że musisz przeformułować problem, aby uniknąć takich oszustw. $L$

Ravi Boppana
źródło

Dzięki, widzę punkt (zdefiniuj L = {M: maszyna Turinga M zatrzymuje się i P ≠ NP}). Oczywiście nie odpowiada to na to, co chciałem zadać, ale myślę, że muszę więcej pomyśleć, aby sformułować pytanie, które chciałem poprawnie zadać.

Tsuyoshi Ito,

Jeśli sztuczny przykład jest naprawdę tak dobry jak naturalny, to naprawdę mogę podać taki przykład!

Edycja: Ponadto, mój przykład jest „nieco” mniejszym oszustwem niż ten sugerowany przez Ravi Boppana (gdzie bierzemy L za pusty język, jeśli P = NP, a problem zatrzymania inaczej), w tym zdefiniuję język L, podając skończoną procedurę, aby zdecydować, czy L dla dowolnego wejścia x. W żadnym momencie nie będzie rozstrzygać, czy x∈L wymaga rozwiązania „nieograniczonego” pytania matematycznego, takiego jak P vs. NP. $x \in$

Bez ceregieli: niech będą wyliczeniem maszyn Turinga do wielu zadań. Dla wszystkich niech będzie leksykograficznie pierwszym który poprawnie decyduje o 3SAT na wszystkich wejściach o długości lub mniejszej. Następnie zdefiniuj język L w następujący sposób: dla wszystkich danych wejściowych rozmiaru , L wtedy i tylko wtedy, gdy maszyna Turinga zakodowana przez zatrzymuje się co najwyżej kroków, gdy jest uruchomiona na czystej taśmie. $M_1, M_2, ...$ $n$ $M_{t(n)}$ $M_i$ $n$ $x$ $n$ $x \in$ $x$ $n^{t(n)}$

Zastrzeżenie 1: Jeśli P = NP, to L P. $\in$

Dowód: jeśli P = NP, to jest pewne ustalone które rozwiązuje 3SAT dla wszystkich danych wejściowych; stąd dla wszystkich . CO BYŁO DO OKAZANIA $M_i$ $t(n) \le i$ $n$

Twierdzenie 2: Jeśli P NP, to L P. $\ne$ $\notin$

Dowód: jeśli wzrasta bez ograniczeń, wówczas możemy po prostu zastosować twierdzenie o hierarchii czasu. CO BYŁO DO OKAZANIA $t(n)$

Teraz nie tylko L nie jest w P przy założeniu, że P NP: zakłada się, że nie będzie w PH (ani nawet PSPACE)! $\ne$

Nawiasem mówiąc, zastanawiam się, czy ktoś może poprawić powyższą konstrukcję, aby uzyskać język L, który jest w P, jeśli P = NP, ale prawdopodobnie nie w PH lub PSPACE, jeśli P NP? $\ne$

Scott Aaronson
źródło

Dzięki! Nie byłem w stanie zmodyfikować konstrukcji, aby udowodnić, że nie należysz do członkostwa w PH, ale to wystarcza, aby mnie przekonać, że dodanie warunku, że L jest rozstrzygalny wraz z konstruktywnym dowodem rozstrzygalności, prawdopodobnie nie zmieni dużo sytuacji. Hmm

Tsuyoshi Ito,

Zaakceptuję odpowiedź Raviego Boppany, ponieważ przyszedł jako pierwszy, chociaż chcę zaakceptować obie, ponieważ obie pozwoliły mi lepiej zrozumieć problem. Mam nadzieje ze rozumiesz….

Tsuyoshi Ito,

Miły. To świetna odpowiedź.

Daniel Apon

@Tyson Williams: Na wszelki wypadek nie zdajesz sobie sprawy, uważaj, aby nie wprowadzić błędu podczas edytowania postu przez innych użytkowników. Na szczęście Joe to zauważył i poprawił.

Tsuyoshi Ito

Odpowiadając na pytanie Scotta Aaronsona, ale trochę za długo na komentarz, oto konstrukcja języka taka, że implikuje , ale implikuje . $L$ $P = NP$ $L \in P$ $P \neq NP$ $L \notin PH$

Niech i jest w budownictwie Scotta. Robimy to, aby nie redukował do dla każdego , ale robimy to tylko, jeśli (tj. Jeśli ). Budowa przebiega etapami. Na etapie (przy użyciu łatwo obliczalnego i łatwo odwracalnego bijection ), zapewniamy, że nie jest wielokrotnością redukcji z do . Niech będzie najmniejszą liczbą całkowitą taką, że $M_1, M_2, M_3, \dotsc$ $t(n)$ $L$ $\Sigma_{k} SAT$ $k$ $t(n) \to \infty$ $P \neq NP$ $s=(i,j)$ $\Sigma^* \to \Sigma^* \times \Sigma^*$ $M_i$ $L$ $\Sigma_{j} SAT$ $n_{s}$ $t(n_{s}) > t(n_{s-1})$ (przypadek podstawowy: ). Jeśli istnieje taka liczba całkowita , to ustaw . Jeśli nie ma takiej liczby całkowitej , pozwalamy być pustym na zawsze. $n_{0} = 1$ $n_{s}$ $L(1^{n_{s}}) = 1 - \Sigma_{k}SAT(M_{i}(1^{n_{s}}))$ $n_{s}$ $L$

Jeśli , to jak , więc zawsze istnieje takie , stąd nie jest w . Jeżeli , a następnie moja jest tylko skończenie różni się od Scotta , a więc jest w . $P \neq NP$ $t(n) \to \infty$ $n \to \infty$ $n_{s}$ $L$ $PH$ $P = NP$ $L$ $L$ $P$

Joshua Grochow
źródło

Dziękuję za odpowiedź, ale nie jestem pewien, czy rozumiem konstrukcję. Wydaje mi się, że aby obliczyć , może być konieczne wyszukiwanie w nieskończoność, dlatego wydaje mi się, że nie mamy wyraźnego algorytmu do decydowania o języku L. Jeśli nie potrzebujemy wyraźnego algorytmu, odpowiedź Ravi Boppana pokazuje że istnieje język L taki, że P = NP⇒L∈P i P ≠ NP⇒L∉R (tj. L jest nierozstrzygalny).

n_{s}

$n_s$

Tsuyoshi Ito,

@Tsuyoshi Ito: Nie sądzę, że masz do obliczenia podane w celu podjęcia decyzji, L; Wszystko, co trzeba zrobić, to na wejściu , decyduje, jeśli jest w postaci dla niektórych i z jakich to zawsze (jeśli występuje). Oto jak: na wejściu , oblicz i oblicz dla wszystkich . Jeśli istnieje takie, że , to nie jest dla dowolnego , więc . W przeciwnym razie dowiedz się, który etap

n_{s}

$n_s$

s

$s$

1^{n}

$1^n$

n

$n$

n_{s}

$n_s$

s

$s$

s

$s$

1^{n}

$1^n$

t (n)

$t(n)$

t (m)

$t(m)$

m < n

$m < n$

m < n

$m < n$

t (n) = t (m)

$t(n)=t(m)$

n

$n$

n_{s}

$n_s$

s

$s$

L (1^{n}) = 0

$L(1^n) = 0$

s

$s$ odpowiada temu (co można zrobić, ponieważ obliczono wszystkie poprzednie wartości ), a następnie obliczyć zgodnie z opisem w odpowiedzi.

n_{s}

$n_s$

t

$t$

L (1^{n})

$L(1^n)$

Joshua Grochow