Ta odpowiedź na główne nierozwiązane problemy w informatyce teoretycznej? pytanie stwierdza, że jest otwarte, jeśli określony problem w NP wymaga czasu .
Patrząc na komentarze pod odpowiedzią, zastanawiałem się:
Oprócz paddingu i podobnych sztuczek, jaka jest najbardziej znana złożoność czasowa dolna granica deterministycznej maszyny RAM (lub deterministycznej maszyny Turinga z wieloma taśmami) dla interesującego problemu w NP (który jest wyrażony w naturalny sposób)?
Czy jest jakiś naturalny problem w NP, o którym wiadomo, że jest nierozwiązywalny w kwadratowym deterministycznym czasie na rozsądnym modelu maszyny?
Zasadniczo to, czego szukam, to przykład wykluczający następujące twierdzenie:
każdy naturalny problem NP można rozwiązać w czasie .
Czy znamy jakikolwiek problem NP podobny do problemu w pracy Karpa z 1972 r. Lub Garey and Johnson 1979, który wymaga deterministycznego czasu ? Czy jest możliwe, zgodnie z naszą najlepszą wiedzą, że wszystkie interesujące naturalne problemy NP można rozwiązać w deterministycznym czasie O ( n 2 ) ?
Edytować
Wyjaśnienie mające na celu usunięcie wszelkich nieporozumień wynikających z niedopasowania dolnej granicy, a nie górnej granicy : szukam problemu, o którym wiemy, że nie możemy go rozwiązać w . Jeśli problem spełnia silniejsze wymaganie, że potrzebny jest czas Ω ( n 2 ) lub ω ( n 2 ) (dla wszystkich wystarczająco dużych sygnałów wejściowych), lepiej, ale nieskończenie często.
źródło
Odpowiedzi:
Adachi, Iwata i Kasai w artykule JACM z 1984 r. Pokazują, że gra Cat and Myszy ma dolną granicę czasu n Ω ( k ) . Problem występuje w P dla każdego k . Problem jest odtwarzany na ukierunkowanym wykresie. Ruchy składają się z kota, a następnie jednego z myszy na przemian z k myszy. Myszy wygrywają, jeśli wylądują na wyznaczonym węźle serowym, zanim kot na nich wyląduje. Pytanie brzmi, czy kot ma wymuszoną wygraną. Jest to w rzeczywistości kompletny problem, więc dolna granica jest naprawdę oparta na diagonalizacji, która daje hierarchię czasu.k nΩ ( k ) k k
Grandjean pokazał, że dolna granica czasu Pippenger, Paul, Szemeredi i Trotter dotyczy kodowania SAT, chociaż wynik Santhanam może go pochłonąć.
Poza wymienionymi w innych komentarzach dolnymi granicami kompromisu czasowo-przestrzennego dla SAT, jest sporo pracy nad dolnymi granicami programu rozgałęziającego, które implikują kompromisy czasoprzestrzenne dla maszyn Turinga. W przypadku problemów takich jak FFT, sortowanie lub obliczanie uniwersalnych funkcji skrótu występują kwadratowe kompromisy w dolnych granicach Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari, ale dotyczą one funkcji o wielu wynikach. W przypadku problemów decyzyjnych w P istnieją dolne granice kompromisu w czasie, które dotyczą granic czasowych, które są ale są one słabsze niż są znane dla SAT.O ( n logn )
źródło
Klasyczny wynik, jaki znam, wynika z Paula, Pippengera, Szemeredi i Trottera (1983) i oddziela deterministyczny od niedeterministycznego czasu liniowego.
Następnie pojawia się bardziej aktualny wynik Fortnow, Lipton, van Melkebeek i Viglas (2004), o którym już wspomniano. Wyjątkowość tego wyniku polega na tym, że jest to wynik kompromisu czasoprzestrzennego, ograniczający zarówno przestrzeń, jak i czas.
Jednak jestem również świadomy wyniku wynikającego z Santhanam (2001), który dowodzi dolnej granicy . Ten wynik jest nieco silniejszy w przypadku ograniczeń czasowych niż powyższy, ale nie daje żadnych gwarancji przestrzeni.ω ( n log∗n-----√)
Biorąc powyższe pod uwagę, jak również moją wiedzę w tej dziedzinie, chciałbym powiedzieć, że udowodnienie, że jest -Complete problem, który nie może być rozwiązany w O ( n 2 ) deterministyczny czas byłoby dość duży krok. O ile mi wiadomo, taki wynik jest uważany za bardzo nieprofesjonalny i prawdopodobnie będzie wymagał nowych technik niższej granicy.N P. O ( n2))
Uwaga: Moje sformułowanie problemu w ostatnim akapicie jest inne niż w pytaniu. Mógłbym być wybredny (i być może nie bardzo pomocny) i powiedzieć, że trywialnie istnieje nieskończona liczba problemów w a zatem w N P , których nie można rozwiązać w czasie deterministycznym O ( n 2 ) przez czas deterministyczny twierdzenie o hierarchii.P. N P. O ( n2))
Edycja: Po dalszym przemyśleniu, oto jak możesz znaleźć problem w który odpowiada Twoim potrzebom:N P.
Powyższe dolne granice powinny utrzymywać nieco złożoność problemu.
Po raz kolejny, jeśli ograniczyć swoją uwagę na -Complete problemów, nie jestem świadomy takich dolnych granic.N P.
źródło
Być może dość naturalny przykład pochodzi z ograniczonej czasowo złożoności Kołmogorowa :
źródło
To po prostu ponownie zadaje to samo pytanie P = NP w inny sposób, jeśli możesz udowodnić, że jest nierozwiązywalny w czasie kwadratowym lub znaleźć absolutną dolną granicę, udowodnisz, że P! = NP
źródło