Problemy, które w praktyce można rozwiązać w sposób sprzeczny z intuicją?

Niedawno przeszedłem przez bolesną zabawę polegającą na nieformalnym wyjaśnianiu koncepcji złożoności obliczeniowej młodemu utalentowanemu samoukiem, programistowi, który nigdy wcześniej nie odbył formalnego kursu algorytmów ani złożoności. Nic dziwnego, że wiele pojęć początkowo wydawało się dziwnych, ale miało sens w niektórych przykładach (PTIME, trudność, niezliczalność) , podczas gdy inne wydają się bardziej naturalne (klasyfikacja problemów poprzez redukcje, czas i przestrzeń jako zasoby, analiza asymptotyczna) . Wszystko szło świetnie, dopóki przypadkiem nie przyznałem, że SATmożna rozwiązać skutecznie * w praktyce ... I właśnie tak, zgubiłem je. Nie miało znaczenia, jak przekonywująco próbowałem argumentować za teorią, dzieciak był przekonany, że to nie wszystko, na czym polega sztuczna bzdura . Dobrze...

¯ \ _ (ツ) _ / ¯

Nie, nie miałem złamanego serca ani nie przejmowałem się tym, co myślał, nie o to chodzi w tym pytaniu. Nasza rozmowa sprawiła, że ​​pomyślałem o innym pytaniu,

Ile naprawdę wiem o problemach, które są teoretycznie nierozwiązywalne (złożoność czasu wielobiegunowego), ale praktycznie możliwe do rozwiązania (za pomocą heurystyki, aproksymacji, rozwiązywaczy SAT itp.)?

Zrozumiałem, niewiele. Wiem, że istnieje kilka bardzo wydajnych rozwiązań SAT, które skutecznie rozwiązują ogromne przypadki, że Simplex działa świetnie w praktyce, a może jeszcze kilka problemów lub algorytmów. Czy możesz mi pomóc namalować pełniejszy obraz? Jakie dobrze znane problemy, a nawet klasy problemów należą do tej kategorii?

TL; DR: Jakie są problemy, które w praktyce można przeciwdziałać intuicyjnie? Czy istnieje (zaktualizowany) zasób, aby przeczytać więcej? Czy mamy dla nich charakterystykę? I wreszcie, jako ogólne pytanie do dyskusji, czyż nie powinniśmy?

EDYCJA 1: Próbując odpowiedzieć na moje ostatnie pytanie w dyskusji na temat takiej charakterystyki , zapoznałem się z płynną analizą algorytmów, koncepcją wprowadzoną przez Daniela Spielmana i Shang-Hua Tenga w [1], która nieustannie interpoluje między najgorszym przypadkiem a analizy algorytmów w średnich przypadkach. Nie jest to dokładnie opisana powyżej charakterystyka, ale zawiera tę samą koncepcję i uważam ją za interesującą.

[1] Spielman, Daniel A. i Shang-Hua Teng. „Płynniejsza analiza algorytmów: dlaczego algorytm simpleks zwykle zajmuje czas wielomianowy”. Dziennik ACM (JACM) 51, nr. 3 (2004): 385–463.

• Wysoce ustrukturyzowane instancje SAT (nawet na milionach zmiennych) często można rozwiązać w praktyce. Jednak losowe instancje SAT w pobliżu progu satysfakcji z nawet kilkuset zmiennymi są nadal otwarte (co oznacza, nawet w praktyce, że jeśli wygenerujesz coś takiego, nigdy nie będziesz wiedział za życia wszechświata, czy wygenerowana rzecz jest zadowalająca, czy nie. za pomocą aktualnych solverów SAT). Możesz być zainteresowany tym powiązanym pytaniem i jego odpowiedziami.

• Wyszukiwarki klik są również szokująco dobre „w praktyce”

  • W odniesieniu do wyszukiwarek klików (część) wyjaśnienia podano w analizie średniego przypadku danych algorytmów.

    Zobacz https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

• Programowanie liczb całkowitych i mieszane programowanie liczb całkowitych-liniowych (z pewnymi zmiennymi racjonalnymi i niektórymi zmiennymi całkowitymi) są przedmiotem zainteresowania całych działów badań operacyjnych i często (choć nie zawsze) można je rozwiązać w praktyce

• $\mathsf{PSPACE}$$\mathsf{PSPACE}$

• $\mathsf{EXPSPACE}$

• Jak już wskazano w komentarzach DW, Graph Isomorphism można praktycznie rozwiązać w praktyce. Bardzo trudno jest zepsuć nowoczesne oprogramowanie GI, takie jak nauty, błogość, pyskaty itp.

System typu Hindley-Milner jest stosowany w funkcjonalnych językach programowania (Haskell, SML, OCaml). Algorytm wnioskowania typu jest w praktyce prawie liniowy i działa zadziwiająco dobrze, ale wiadomo, że jest on ukończony w trybie DEXPTIME!

Ogólny komentarz: nic dziwnego, że złożoność w najgorszym czasie niekoniecznie jest bardzo dobrą miarą praktycznej wydajności algorytmu. Jednak stwierdzenie, że rozbieżność między teorią a praktyką czyni teorię złożoności bezużyteczną, jest jak powiedzenie, że liczby naturalne są marnotrawstwem, ponieważ używamy tylko niewielkiej ilości wszystkich dostępnych liczb. Słynny filozof powiedział kiedyś, że „Doświadczenie bez teorii jest ślepe, ale teoria bez doświadczenia jest jedynie intelektualną grą”.

Więcej przykładów, głównie z języków programowania:

1. k-CFA (k-Control Flow Analysis) jest EXPTIME-complete (Van Horn i Mairson 2008), ale kompilatory optymalizujące cały program, takie jak MLton, i tak go wykonują. Czasy kompilacji są długie, ale rzadko katastrofalne.
2. Rozwiązanie (dynamiczne) przeciążenie jest na ogół NP-całkowite (Palsberg 2012). Ale w rzeczywistości rzadko stanowi to problem.
3. $k$
4. Rozwiązywanie SMT jest na ogół kompletne NP, ale komercyjne solwery SMT (takie jak Z3 i CVC4) są zwykle dość wydajne. Nie współpracuję bezpośrednio z solverami SMT, ale używałem Z3 pośrednio od Liquid Haskell i Dafny, a czasy sprawdzania wydają się OK.
5. Problem decyzyjny dla arytmetyki Presburger jest naprawdę złożony (Fischer i Rabin 1974), ale algorytm decyzyjny Billa Pugha, test Omega (Pugh 1991), działa zasadniczo w czasie wielomianowym niskiego rzędu.

$O$$n$$n$

Referencje:

[1] David Van Horn i Harry G. Mairson. 2008. Podjęcie decyzji o kCFA zostało zakończone na EXPTIME. W materiałach 13. Międzynarodowej Konferencji Programowania Funkcjonalnego ACM SIGPLAN (ICFP '08). ACM, Nowy Jork, NY, USA, 275–282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] MJ Fischer i MO Rabin. 1974. NAJWYŻSZA WYKŁADNOŚĆ ARTYMMU PRESBURGERA. Raport techniczny. Massachusetts Institute of Technology, Cambridge, MA, USA.

[4] William Pugh. 1991. Test Omega: szybki i praktyczny algorytm programowania liczb całkowitych do analizy zależności. W materiałach z konferencji ACM / IEEE z 1991 r. Na temat superkomputerów (Superkomputer '91). ACM, Nowy Jork, Nowy Jork, USA, 4-13.

okazuje się, że szkolenie sieci neuronowych przy użyciu metod opadania gradientu jest bardzo trudnym problemem np. https://www.cs.utexas.edu/~klivans/crypto-hs.pdf, ale ogólnie można je rozwiązać w praktyce.