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

25

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 .Ω(n2)

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(n2)

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 ) ?Ω(n2)O(n2)

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(n2)Ω(n2)ω(n2)

Anonimowy
źródło
5
jedyne superliniowe dolne granice, jakie znam dla naturalnych problemów w NP, to kompromisy w przestrzeni czasowej dla SAT ( dl.acm.org/citation.cfm?doid=1101821.1101822 , a kontynuacja pracy @RyanWilliams, która będzie wiedziała znacznie więcej) . i nic nie mówią, jeśli przestrzeń może być liniowa.
Sasho Nikolov
@SashoNikolov, wyniki czasoprzestrzeni dotyczą SAT i nie ma żadnych redukcji z wielu naturalnych problemów NP do SAT, gdzie wielkość wyjścia jest liniowo ograniczona do wielkości wejścia. dolny związany przez pewien naturalny NP problemu konieczności nie wiąże się ze wzmocnieniem wyniku dla SAT niż aktualnie znane. Ω(n2)
Anonimowy
1
mówię, że nie znam żadnej superliniowej dolnej granicy dla jakiegokolwiek innego naturalnego problemu NP
Sasho Nikolov
W jaki sposób używasz wypełniania, aby uzyskać sztuczny problem w NP z dolną granicą złożoności czasowej ? Ω(n2)
Robin Kothari,
@RobinKothari, weź problem w czasie DTIME ( ) i wypełnij go. Dowód opiera się na niedeterministycznym twierdzeniu o hierarchii czasu, a wypełnienie nie było właściwym sposobem odniesienia się do przykładu. Możemy wziąć problem NP w czasie NTIME ( Ω ( n 2 ) ) bezpośrednio. Ω(2n)Ω(n2)
Anonimowy

Odpowiedzi:

16

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.knΩ(k)kk

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(nlogn)

Paul Beame
źródło
jakiś pomysł na związek gry kot-mysz z NP?
vzn
12

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.ω(nlogn)

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.NPO(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.PNPO(n2)


Edycja: Po dalszym przemyśleniu, oto jak możesz znaleźć problem w który odpowiada Twoim potrzebom: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)=Ω(n2logn)ω(n2)
  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)=ω(n2)
  3. Każdy naturalny problem z dolną granicą , gdzie f ( n ) = ω ( n 2 / log n ) . Jest to uzasadnione separacją TIME-SPACE. Wierzę w toSPACE(f(n))f(n)=ω(n2/logn)

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.NP

chazisop
źródło
3
pytanie dotyczy naturalnego problemu
Sasho Nikolov
Dziękuję, ale nie pytam o czas deterministyczny vs. niedeterministyczny: możesz wziąć dowolny problem w czasie NTIME ( ), o ile wymaga on czasu deterministycznego Ω ( n 2 ) . Ani drugi wynik nie odpowiada na moje pytanie nie dlatego, że ogranicza przestrzeń, ale ponieważ dotyczy tylko SAT, zobacz moją odpowiedź dla Sasho Nikolova pod pytaniem. I są problemy NP-zupełne, których nie można rozwiązać w deterministycznie Ω ( n 2 ) przez wypełnienie, szukam naturalnych przykładów. nkΩ(n2)Ω(n2)
Anonimowy
@ Anonimowy, czy mówisz, że SAT nie jest naturalnym problemem?
Sasho Nikolov
@SashoNikolov, SAT jest naturalnym problemem. Jednak wynik nie odpowiada na moje pytanie pozytywnie. Dlatego zinterpretowałem to jako powiedzenie, że nie jest znana lepsza odpowiedź na moje pytanie. Tak nie musi być. W tym sensie nie odpowiada na moje pytanie.
Anonimowy
2
Spróbuję ostatni raz: chociaż masz rację, że nie ma takiej implikacji, jestem całkiem pewien, że nie jest znana bezwarunkowa kwadratowa dolna granica względem deterministycznego czasu dla jakiegokolwiek naturalnego problemu NP. Nie wynika to z wyników SAT; to tylko stan rzeczy
Sasho Nikolov
2

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

kf(n)nxM|M|<f(|x|)Mx|x|k

Marzio De Biasi
źródło
Dziękuję, nie jest to całkowicie sztuczne, ale nie uważam tego za satysfakcjonujący naturalny przykład.
Anonimowy
2
Ω(nk)
@SashoNikolov: Usunąłem część Ramsey ... potrzebuje formalnego dowodu :-(
Marzio De Biasi
-7

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

Alex Gonopolskiy
źródło
11
Dlaczego kwadratowa dolna granica naturalnego problemu w NP pokazuje P! = NP?
Robin Kothari,