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