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 L. ). 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.
źródło
Odpowiedzi:
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.
źródło
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).
źródło