Czy ALogTime! = PH jest trudne do udowodnienia (i nieznane)?

Lance Fortnow stwierdził ostatnio, że udowodnienie L! = NP powinno być łatwiejsze niż udowodnienie P! = NP :

Oddziel NP od przestrzeni logarytmicznej. Podałem cztery podejścia w ankiecie przeprowadzonej przed blogiem w 2001 r. Na temat diagonalizacji (sekcja 3), chociaż żadna z nich się nie podjęła. Powinno być znacznie łatwiejsze niż oddzielenie P od NP.

Sekcja 3 w połączonej ankiecie twierdzi, że nie ma znaczących wyników upadku wyroczni:

Podczas gdy pytanie P! = NP pozostaje dość groźne, pytanie L! = NP wydaje się znacznie bardziej wykonalne. Nie mamy powodu sądzić, że to pytanie jest trudne. Brak dobrych modeli relatywizacji przestrzeni oznacza, że nie mamy żadnego sensownego modelu wyroczni, w którym L i NP się zapadają. Ponieważ L jest klasą jednolitą, ograniczenia Razborova-Rudicha [RR97] nie mają zastosowania.

Pytanie o znanych barier relatywizacji do L! = NP na tej stronie dostałem odpowiedź wskazując, że PSPACE-complete problemem TQBF może być stosowany jako wyroczni, aby dostać taki upadek. Wydaje się również, że na zastrzeżenie, czy był to sensowny model wyroczni.

Ale nawet gdybym zrozumiał, dlaczego „nie mamy sensownego modelu wyroczni, w którym L i NP zapadają się” należy uznać za prawidłowe stwierdzenie, nadal mam wątpliwości, czy udowodnienie L! = NP jest bardziej wykonalne niż udowodnienie P! = NP. Jeśli udowodnienie L! = NP powinno być naprawdę łatwiejsze niż udowodnienie P! = NP, to udowodnienie ALogTime! = PH powinno zdecydowanie być w zasięgu ręki. (Artykuł w ankiecie wskazuje na możliwość oddzielenia od ). Myślę, że ALogTime! = PH jest nadal otwarty i chciałbym wiedzieć, czy istnieją dobre powody, aby oczekiwać, że będzie to trudne do udowodnienia. $\Sigma_2^p$ $L$

cc.complexity-theory reductions relativization

— Thomas Klimpel
źródło

Lance Fortnow 7:03 AM, 13 maja 2016 : „Pozwólcie, że przeformułuję mój punkt. Niech AP będzie naprzemiennie polytime (znany jako PSPACE nierelatywizowany i tym samym różny od L). Wtedy nie jest znany model relatywizacji, który sprawia, że L = NP dla niektórych wyroczni, ale oddziela L od AP dla wszystkich wyroczni. ”

— Thomas Klimpel

Odpowiedzi:

$L$ $NP$ $L = NL$ $L^A = NL^A$ $A$

$NC1$ $ALogTime = NP$ $NC1$ $NP$ $NC1$

Poza tym nie znam żadnego szczególnego powodu, by sądzić, że „trudno jest udowodnić” poza spostrzeżeniem, że wiele osób próbowało i nikomu jeszcze się nie udało.

— Ryan Williams
źródło

L = N L

$L = NL$

L^{A} = N L^{A}

$L^A = NL^A$

A

$A$

L

$L$

Wierzę, że jest dowód na oświadczenie w artykule, który podłączyłem. Co do drugiego zdania: pytasz, dlaczego Fortnow twierdzi, że Razborov-Rudich nie ma zastosowania? Jeśli tak, to chodzi mu o to, że powszechnie rozumiana bariera dowodów naturalnych ma zastosowanie tylko wtedy, gdy model, na który się opierasz, jest nierównomierny, np. P / poli.

— Ryan Williams

Ach, źle odczytałem: Myślałem, że barierą, która nie miała zastosowania, była relatywizacja, a nie naturalne dowody, przepraszam. Chciałem zapytać: dlaczego relatywizacja jest moralnie barierą dla P w porównaniu z NP, ale nie w porównaniu z L w stosunku do NL? (Stąd brak związku pytania).

— Michaël Cadilhac

Krótko mówiąc, dzieje się tak, ponieważ model wyroczni RST nie pozwala na wykonywanie niedeterministycznych kroków, chyba że taśma wyroczni jest pusta. (Przyczyny tego są subtelne; w zasadzie niektóre wyniki nie są relatywizowane bez niego.) Rzeczywisty argument jest bardziej skomplikowany ...

— Ryan Williams

Naiwny pomysł na udowodnienie ALogTime! = PH: Problem wartości formuły logicznej jest kompletny dla ALogTime przy deterministycznych redukcjach czasu dziennika . Zatem jeśli ALogTime = PH, to PH = coNP = ALogTime, a zatem problem wartości formuły logicznej byłby kompletny przy deterministycznych redukcjach czasu dziennika dla coNP. Stąd nastąpiłoby deterministyczne skrócenie czasu dziennika od problemu tautologii do problemu wartości formuły logicznej.

Deterministyczne skrócenie czasu dziennika powinno być nieszkodliwe, nie mogą one w znacznym stopniu przyczynić się do rozwiązania problemu tautologii. Są po prostu ładną formalizacją, co oznacza, że redukcja może działać tylko lokalnie. Dlatego pozostałym zadaniem jest zrozumienie, dlaczego problem tautologii nie może zostać przekształcony w problem wartości formuły logicznej przez bardzo lokalne redukcje. Nadal nie wiem, jak to zrobić, ale przynajmniej pozostałe zadania są bardzo jasne, więc mam przynajmniej szansę zrozumieć, dlaczego jest to trudne (lub nie).

— Thomas Klimpel
źródło