Problemy, które wydają się wykładnicze, ale są P

Próbuję zbudować listę algorytmów / problemów, które są „wyjątkowo przydatne”, jak w przypadku rozwiązywania problemów, które „wydają się” z natury bardzo wykładnicze, ale mają jakiś szczególnie sprytny algorytm, który ostatecznie je rozwiązuje. Przykłady tego, co mam na myśli:

• Programowanie liniowe (algorytm simpleksowy jest czasem wykładniczym; znalezienie rozwiązania wielomianowego czasu zajęło dużo czasu!)
• Mówiąc bardziej ogólnie, programowanie semidefinite
• Testy pierwotności
• 2-SAT i HORNSAT
• Obliczanie uwarunkowań (jeśli nie wydaje się to trudne, rozważ stałe)
• Znalezienie idealnych dopasowań
• Różnorodne trudne teoretyczne problemy grupowe, które można rozwiązać za pomocą Klasyfikacji skończonych grup prostych
• Różnorodne trudne problemy z grafem, które można rozwiązać za pomocą skomplikowanych charakterystyk Zakazanych Drobnych (możliwość osadzenia na dowolnej powierzchni; ograniczenie szerokości i szerokości gałęzi; wykresy redukcyjne Delta-Wye)
• Obliczanie wykładniczych w ograniczonej grupie (tj. Obliczanie kroków $a^b \mod k$ w $\log b$ , co jest osiągane przez powtarzanie kwadratu)
• Obliczenia oparte na algorytmie LLL. (Jako szczególny przypadek: algorytm euklidesowy. Jako bardziej ogólny przypadek: algorytmy PSLQ lub HJLS.)
• Problemy z ograniczeniami bez warunków Taylora (?). Przyznaję, że nie do końca to rozumiem, ale wygląda na to, że prawdopodobnie obejmuje powyższe przypadki 2-SAT / HORNSAT i jakąkolwiek algebrę liniową nad polami skończonymi. Zobacz tutaj na dłuższy słupek
• Problemy obliczalne przez redukcje holograficzne .

Jako wyróżnienie chciałbym również wspomnieć o izomorfizmie grafów, ponieważ wciąż jest on okropnie łatwy ( ) i równoważny tak wielu innym problemom z izomorfizmem:$n^{\log^2 n}$

• Digraphs / multigraphs / hypergraphs (rodzaj „trudniejszego” problemu)
• Automaty skończone / CFG

Oczywiście jest w tym wiele trudności, ale wszyscy pozostawiają przynajmniej niektórych ludzi z poczuciem „zaskoczenia” w tym sensie, że problem może wydawać się trudny, ale okazuje się możliwy do rozwiązania. LP może wydawać się stosunkowo proste, ale zajęło ludziom sporo czasu, aby zbudować rzeczywiste rozwiązanie. Powtarzanie kwadratu lub rozwiązywania 2-SAT jest czymś, co student mógłby wymyślić samodzielnie, ale jeśli nauczyłeś się tylko o problemach z NP-Complete bez zobaczenia HORNSAT, może to brzmieć jak naturalny kandydat na NP-Kompletność. Rozwiązanie CFSG lub posiadanie wielomianowego sposobu sprawdzania możliwości redukcji Delta-Wye to nie lada wyczyn.

Mam nadzieję, że to ma sens; jest tu oczywiście wiele subiektywnych atrybutów, ale ciekawi mnie, co inni uważają za skuteczne rozwiązania „oczywiście trudnych” problemów.

Dla mnie jednym z najbardziej wydajnych algorytmów jest algorytm Blossom V, który znajduje idealne dopasowanie maksymalnej masy na ogólnym wykresie:

https://en.m.wikipedia.org/wiki/Blossom_alameterm

Dla mnie wszystkie klasyczne i nowsze, bardziej wydajne algorytmy do weryfikacji lub znalezienia minimalnego drzewa opinającego (MST) połączonego wykresu ważonego krawędziami są dobrymi kandydatami. Wiele z tych algorytmów wymieniono w Wikipedii .

Na pierwszy rzut oka problem ten wygląda jak problem podróżnego sprzedawcy, jeden z niewielu najsłynniejszych problemów NP-trudnych. Co zadziwiające, istnieją algorytmy liniowe do weryfikacji MST i wiele algorytmów prawie liniowych do znalezienia MST! W rzeczywistości jednym z najbardziej znanych otwartych problemów w algorytmach jest to, czy istnieje deterministyczny algorytm liniowy do znalezienia MST na ogólnych wykresach. Okazuje się, że istnieje bogata struktura i właściwości matematyczne i graficzne, a także wiele praktycznych zastosowań związanych z MST, co czyni go jednym z bardziej przyjemnych i rozwijalnych tematów na kursie informatyki. Aby zapoznać się z nieco przestarzałym, ale bardzo dobrze napisanym kompleksowym wprowadzeniem, zapoznaj się z samouczkiem Jasona Eisnera .