Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP

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 .$\Omega(n^2)$

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 .$O(n^2)$

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 ) ?$\Omega(n^2)$$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.$o(n^2)$$\Omega(n^2)$$\omega(n^2)$

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^{\Omega(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 \log n)$

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.$\omega (n \sqrt{ \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.$\mathbb{NP}$$O(n^{2})$

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.$\mathbb{P}$$\mathbb{NP}$$O(n^{2})$

Edycja: Po dalszym przemyśleniu, oto jak możesz znaleźć problem w który odpowiada Twoim potrzebom:$\mathbb{NP}$

1. Każdy naturalny problem z dolną granicą , gdzie f ( n ) = Ω ( n 2 log n ) . Twierdzenie o hierarchii DTIME wymaga czasu ω ( n 2 ) . Wierzę, że istnieje ich kilka.$DTIME ( f(n) )$$f(n) = \Omega ( n^{2} \log n)$$\omega( n^{2} )$
2. Każdy naturalny problem z dolną granicą , gdzie f ( n ) = ω ( n 2 ) , przy użyciu hierarchii NTIME. Nie znam żadnych takich naturalnych problemów.$NTIME ( f(n) )$$f(n) = \omega ( n^{2} )$
3. Każdy naturalny problem z dolną granicą , gdzie f ( n ) = ω ( n 2 / log n ) . Jest to uzasadnione separacją TIME-SPACE. Wierzę w to$SPACE ( f(n) )$$f(n) = \omega ( n^{2} / \log n)$

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.$\mathbb{NP}$

Być może dość naturalny przykład pochodzi z ograniczonej czasowo złożoności Kołmogorowa :

$k$$f(n) \leq n$$x$$M$$|M| < f(|x|)$$M$$x$$|x|^k$

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