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ć.Θ ( 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ć?
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.
źródło
Odpowiedzi:
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⌈k/2⌉) n7 n6.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 dlak k k 2k O(n2) n 2k k 0 O(nk/2−ε) k O(nk−2ε) 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(logn) O(n2) 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[n2] TIME[n2] 3 3 O(logn) 3 P≠NP n2 (W pewnym momencie „3SUM-hard” nazwano „ -twardym ”; ten artykuł SIGACT słusznie narzekał na tę nazwę).n2
źródło
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.Ω⋆(n3)
źródło
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(nd) 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 .k Ω ( n ⌊ d / 2 ⌋ + 1 ) d ≥ 3(d+1) k Ω(n⌊d/2⌋+1) d≥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
źródło
źródło