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

12

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 abmodk w logb , 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:nlog2n

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

Alex Meiburg
źródło
Jako motywację do tego pytania (ponieważ również zadawał mu to przyjaciel): Często mówimy o tym, jak ważne jest nauczanie uczniów o kompletności NP i nierozstrzygalności, ponieważ pomaga im rozpoznać, kiedy problemy będą zbyt trudne i powinni ich unikać. Ta lista to „problemy, które możesz pomylić z NP-Complete, ale możesz to zrobić”. Nie oczekuję, że wielu uczniów wypełni się pod wrażeniem, że wyznaczniki nie mogą być obliczone - tak jak prawdopodobnie nie napotkają 3SAT na wolności - ale powinni rozpoznać inne równoważne problemy
Alex Meiburg
1
Podejrzewam, że jest to zbyt szerokie, aby pasowało do naszej witryny. Pytanie o wyczerpującą listę czegoś nie brzmi jak pytanie, które działa tutaj dobrze. „Jestem ciekawy, co znajdują inni ludzie…” brzmi jak pytanie, które tutaj nie jest odpowiednie; zobacz nasze centrum pomocy .
DW
1
Rozumiem, starałem się uznać subiektywność w tym pytaniu, ale myślę, że to pytanie jest w dużej mierze czymś, co ludzie zgodzą się i wyciągną wnioski z owocnej dyskusji. Jeśli masz pytania, które brzmią: może (chociaż znam inną witrynę), zobacz cstheory.stackexchange.com/questions/20930/… lub cstheory.stackexchange.com/questions/11119/… ?
Alex Meiburg
Nie jest też wcale jasne, co „odczuwa” wykładniczy komu.
Raphael

Odpowiedzi:

2

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

Dmitrij Kamieniecki
źródło
1
To dobry przykład! Nigdy tak naprawdę o tym nie myślałem ani nie potrzebowałem. Wydaje mi się, że miałem wrażenie, że maksymalne dopasowanie na dowolnych wykresach było trudne dla NP. :)
Alex Meiburg
1

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 .

John L.
źródło