Problemy, które mogą być wykorzystane do pokazania wyników twardości w czasie wielomianowym

58

Gdy projektuję algorytm dla nowego problemu, jeśli po pewnym czasie nie mogę znaleźć algorytmu wielomianowego czasu, mogę spróbować udowodnić, że jest to trudny NP. Jeśli mi się uda, wyjaśniłem, dlaczego nie mogłem znaleźć algorytmu czasu wielomianowego. Nie chodzi o to, że wiem na pewno, że P! = NP, to po prostu, że jest to najlepsze, co można zrobić przy obecnej wiedzy, i rzeczywiście istnieje konsensus, że P! = NP.

Podobnie powiedzmy, że znalazłem rozwiązanie czasu wielomianowego dla jakiegoś problemu, ale czas działania wynosi . Po wielu wysiłkach nie robię postępów w ulepszaniu tego. Zamiast tego mogę spróbować udowodnić, że jest to 3SUM-hard. Zazwyczaj jest to zadowalający stan rzeczy, nie z powodu mojego najwyższego przekonania, że 3SUM rzeczywiście wymaga czasu, ale ponieważ jest to obecny stan techniki, a wielu inteligentnych ludzi próbowało poprawić i zawiodło. Więc to nie moja wina, że to najlepsze, co mogę zrobić. $O(n^2)$ $\Theta(n^2)$

W takich przypadkach najlepszym, co możemy zrobić, jest wynik twardości zamiast rzeczywistej dolnej granicy, ponieważ nie mamy żadnych superliniowych dolnych granic dla maszyn Turinga dla problemów w NP.

Czy istnieje jednolity zestaw problemów, które można zastosować dla wszystkich wielomianowych czasów działania? Na przykład, jeśli chcę udowodnić, że jest mało prawdopodobne, że jakiś problem ma algorytm lepszy niż , to czy jest jakiś problem X, który mogę pokazać, że jest X-trudny i na tym zostawić? $O(n^7)$

Aktualizacja : To pytanie pierwotnie dotyczyło rodzin problemów. Ponieważ nie ma tak wielu rodzin problemów, a to pytanie otrzymało już doskonałe przykłady indywidualnych trudnych problemów, odsuwam pytanie do każdego problemu, który można zastosować do wyników twardości w czasie wielomianowym. Dodam również nagrodę za to pytanie, aby zachęcić do dalszych odpowiedzi.

cc.complexity-theory lower-bounds conditional-results

— Robin Kothari
źródło

5

Strona maven.smith.edu/~orourke/TOPP/P11.html podsumowuje niektóre wyniki dotyczące dolnych (i górnych) granic 3SUM i powiązanych problemów i jest warta przeczytania.

— Tsuyoshi Ito

2

Brak superliniowych dolnych granic dotyczy TM z co najmniej dwiema taśmami, prawda? Pamiętam, że czytałem gdzieś, że sprawdzanie palindromu na jednej taśmie TM ma dolną granicę czasu kwadratowego. Kiedy mówimy o dolnych granicach w obrębie , w rodzaju vs. , czy nadal można założyć, że dokładny model TM nie ma większego znaczenia?

P

$P$

Ω (n^{i})

$\Omega(n^i)$

Ω (n^{i + 1})

$\Omega(n^{i+1})$

— gphilip

3

Poza tematem: Robin, Tsuyoshi, dziękuję za wprowadzenie rodziny niższych granic 3SUM: nigdy wcześniej o nich nie słyszałem.

— gphilip

2

@Tsuyoshi: Dzięki za informację. To miła ankieta na ten temat: cs.mcgill.ca/~jking/papers/3sumhard.pdf . @ gphilip: Niedawno przedstawiłem ten problem niektórym geometrom obliczeniowym. Myślę, że jest to bardzo dobrze znane w tej dziedzinie.

— Robin Kothari,

Świetne pytanie. Czy możesz wyjaśnić, co rozumiesz przez „jednolity”: czy chcesz ograniczyć ilość wstępnego przetwarzania parametru?

— András Salamon,

35

Tak, najbardziej znany algorytm dla SUMA działa w czasie , więc jest bardzo możliwe, że możesz argumentować, że jakiś problem z jest trudny, ponieważ jeśli jest w wtedy możesz rozwiązać SUM szybciej. $k$ $O(n^{\lceil k/2 \rceil})$ $n^7$ $n^{6.99}$ $14$

Zauważ, że problem SUM staje się „łatwiejszy” wraz ze wzrostem : biorąc pod uwagę ulepszony algorytm dla SUM, dość łatwo jest uzyskać ulepszony algorytm dla -SUM: weź wszystkie pary liczb w swoim biorąc pod uwagę instancję -SUM, zastępując każdą parę sumą dwóch, i poszukaj sumy liczb spośród tych, które są równe . Następnie algorytm dla SUM implikuje algorytm dla SUM. Innymi słowy, ciasna dolna granica dla $k$ $k$ $k$ $2k$ $O(n^2)$ $n$ $2k$ $k$ $0$ $O(n^{k/2-\varepsilon})$ $k$ $O(n^{k-2\varepsilon})$ $2k$ $2k$ -SUMA jest silniejszym założeniem niż ciasna dolna granica dla -SUM. $k$

Innym kandydatem na trudny problem jest klika. Zobacz moją odpowiedź -Kliknij, aby dowiedzieć się więcej na ten temat . Jeśli potrafisz pokazać (na przykład), że lepszy algorytm dla twojego problemu oznacza algorytm dla kliki, wówczas wymagany byłby przełom, aby ulepszyć twój algorytm. Sparametryzowana złożoność daje wiele przykładów innych problemów, takich jak ten: Klika jest trudna dla klasy , a -SUM jest trudna dla . $k$ $O(\log n)$ $O(n^2)$ $3$ $k$ $W\[1\]$ $k$ $W\[2\]$

Ostrzegam, że chociaż takie problemy są bardzo wygodne w pracy, problemy takie jak SUM nie należą do „najtrudniejszych” w , np. Jest bardzo mało prawdopodobne, aby każdy problem w można faktycznie zredukować czas liniowy do SUM. Wynika to z faktu, że SUMA można rozwiązać za pomocą bitów niedeterminizmu w czasie liniowym, więc jeśli wszystko w czasie kwadratowym można zredukować do SUM, to i inne fantastyczne konsekwencje skutkują. Więcej na ten temat można znaleźć w artykule „Jak trudne są problemy z twardością ?” $3$ $TIME[n^2]$ $TIME[n^2]$ $3$ $3$ $O(\log n)$ $3$ $P \neq NP$ $n^2$ (W pewnym momencie „3SUM-hard” nazwano „ -twardym ”; ten artykuł SIGACT słusznie narzekał na tę nazwę). $n^2$

— Ryan Williams
źródło

4

Jedyny problem, jaki mam z użyciem k-kliki, polega na tym, że 3-klika jest rozwiązywalna w . Gdyby tak było, gdyby klika k wymagała , byłaby to świetna naturalna rodzina do użycia.

O (n^{2} .376)

$O(n^2.376)$

Θ (n^{k})

$\Theta(n^k)$

— Robin Kothari,

Nie widzę zasadniczej różnicy między użyciem SUMA i Kliki. -SUMA jest w dla parzystego . Jeśli możesz wykazać, że lepszy algorytm dla twojego problemu sugeruje, że Klika ma wartość , jest to mocny dowód na to, że trudniej jest znaleźć lepszy algorytm dla twojego problemu.

k

$k$

k

$k$

k

$k$

O (n^{k / 2})

$O(n^{k/2})$

k

$k$

k

$k$

O (n^{k / 2})

$O(n^{k/2})$

— Ryan Williams

miłe referencje, Ryan. Wstydzę się, że nie wiedziałem o tym wcześniej, biorąc pod uwagę popularność 3SUM w społeczności geometrii. Oczywiście rodzi się pytanie: czy są jacyś naturalni kandydaci na ?

n^{2}

$n^2$

— Suresh Venkat

@Ryan: Masz rację, są takie same. Chociaż w przypadku k-SUM przynajmniej w słabszych modelach mamy dowody, że przypuszczalna granica jest poprawna. Nie znam żadnych argumentów sugerujących, że 3-klika nie powinna być rozwiązana szybciej niż mnożenie macierzy.

— Robin Kothari,

@Robin: Myślałem, że każda naturalna rodzina problemów z prawdopodobnymi dolnymi granicami , dla , byłaby dobrą odpowiedzią. Dokładna stała wydaje się mniej ważna?

n^{f (k)}

$n^{f(k)}$

f (k) = Θ (k)

$f(k) = \Theta(k)$

— András Salamon,

14

Uważa się, że problem najkrótszych ścieżek wszystkich par (APSP) wymaga czasu. Zmniejszenie go to świetny sposób na argument, że ulepszenia oparte na szybkim mnożeniu macierzy (FMM) są mało prawdopodobne. $\Omega^\star(n^3)$

— Mihai
źródło

2

A co ze średnicą wykresu? Jeszcze lepiej, zrób z tego problem decyzyjny „Czy średnica wynosi co najmniej k?”. O ile mi wiadomo, ma to tę zaletę, że nie ma oczywistej granicy superliniowej.

— Raphael,

9

Uważa się, że najlepsze algorytmy dla problemu degeneracji afinicznej w przestrzeni wymiarowej działają w czasie . Problem jest następujący: Biorąc pod uwagę punktów w przestrzeni wymiarowej ze współrzędnymi całkowitymi, czy jakieś punkty leżą na wspólnej hiperpłaszczyźnie? $d$ $O(n^d)$ $n$ $d$ $d+1$

Problem degeneracji afinicznej jest -SUMOWY twardy. Jeśli podłączymy przypuszczalną dolną granicę dla SUMA, otrzymamy dolną granicę . Jednak przypuszczenie o złożoności problemu degeneracji afinicznej jest znacznie silniejsze w przypadku . $(d+1)$ $k$ $\Omega(n^{\lfloor d/2 \rfloor +1})$ $d \geq 3$

J. Erickson, S. Har-Peled i DM Mount, On the Least Median Square Problem, Discrete and Computational Geometry, 36, 593-607, 2006. http://www.cs.umd.edu/~mount/Papers /dcg06-lms.pdf

J. Erickson i R. Seidel. Lepsze dolne granice przy wykrywaniu drobnych i sferycznych zwyrodnień. Discrete Comput. Geom., 13: 41–57, 1995. http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html

J. Erickson. Nowe dolne granice problemów wypukłego kadłuba w nieparzystych wymiarach. SIAM J. Comput., 28: 1198–1214, 1999. http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html

— Guilherme D. da Fonseca
źródło

Podoba mi się ta odpowiedź, ale czy mógłbyś to wyjaśnić? Dlaczego się w to wierzy?

— Aaron Sterling

8

$\Theta(n^{4/3})$ $n$ $n$

— Jeffε
źródło

7

czy są jakieś problemy niegeometryczne, które sprowadzają się do problemu Hopcroft?

— Suresh Venkat

Postanowiłem przyznać nagrodę za tę odpowiedź, ponieważ nigdy wcześniej nie słyszałem o tym problemie.

— Robin Kothari,