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

21

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.

cc.complexity-theory ds.algorithms np-hardness

— Konstantinos Koiliaris
źródło

6

Co miałeś na myśli mówiąc, że SAT można skutecznie rozwiązać w praktyce? Dlaczego twój przyjaciel polega na bezpieczeństwie w Internecie? Czy w praktyce nie ma żadnych trudnych problemów? Solidność jest jedną z głównych zalet wielozadaniowości / efektywnej wypłacalności.

— Chandra Chekuri

6

Wykres izomorfizm jest naturalnym kandydatem.

— DW

2

Hej, ChandraChekuri, miałem na myśli to, że praktycznie solwery SAT mogą odpowiadać na instancje SAT milionami zmiennych i klauzul. A przynajmniej tak myślałem. Nie jestem pewien, czy rozumiem, co masz na myśli przez „bezpieczeństwo w Internecie”? Nie sprzeciwiam się formalizmowi, interesują mnie problemy, które teoretycznie są nierozwiązywalne, ale ze względów praktycznych (może z powodu przyzwoitego zbliżenia, może ze względu na specjalną strukturę instancji w świecie rzeczywistym itp.) Uważa się je za „ uległy".

— Konstantinos Koiliaris

1

@KonstantinosKoiliaris Myślę, że chodziło o to, że bezpieczeństwo wszystkich rodzajów protokołów kryptograficznych zależy od

(zwykle nawet czegoś znacznie silniejszego) i jako takie dostarcza wielu przykładów problemów z rutynowej praktyki, które są niezwykle trudne dla solverów SAT ( tak czy inaczej mamy taką nadzieję).

P \neq N P

$P\ne NP$

— Emil Jeřábek wspiera Monikę

2

W tym duchu warto sprawdzić ogólną złożoność. W rzeczywistości okazuje się, że problem zatrzymania można prawie zawsze rozwiązać w czasie wielomianowym, podobnie jak na przykład SAT (w rzeczywistości SAT ma silniejszą gwarancję). „Prawie zawsze” oznacza, że problem dopuszcza algorytm taki, że proporcja danych wejściowych, dla których algorytm zatrzymuje się (i oczywiście podaje poprawną odpowiedź) w czasie wielomianowym, wzrasta wraz ze wzrostem długości danych wejściowych.

— Guillermo Angeris

17

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.

— Joshua Grochow
źródło

Dzięki Joshua, daję ci to za najbardziej interesujące / ogólne sugerowane problemy.

— Konstantinos Koiliaris

1

Wyszukiwarki klik nie zawsze są dobre w praktyce. To naprawdę zależy od wykresu. A twój link wydaje się mówić tylko o losowych wykresach.

— Peter Shor

Rozwijając nieco temat GI: AFAIK w najbardziej zaawansowanych rozwiązaniach GI, takich jak wspomniane, wykorzystuje zoptymalizowane podejście do indywidualizacji i udoskonalania (gdzie udoskonaleniem jest udoskonalenie kolorów, które już działa jako quasilinearny test GI dla prawie wszystkich grafów) , ale Neuen i Schweitzer pokazali ostatnio wykładniczą dolną granicę dla tej metody i skonstruowali (praktycznie) trudne instancje.

— Watercrystal

1

@JoshuaGrochow: Tak, zgadzam się z tobą w tej sprawie. Chciałem tylko rozwinąć „sprzeczną z intuicją” część pytania, ponieważ OP wyraźnie wspomniało, że Simplex działa bardzo dobrze w praktyce, mimo że znane są wykładnicze dolne granice i mamy tę samą sytuację.

— Watercrystal

1

Mam tylko doświadczenie z hipotezą Kellera , w której (co prawda duże) wykresy zakłócają wiele algorytmów wyszukiwania klików.

— Peter Shor

14

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ą”.

— Andrej Bauer
źródło

F P L

$\mathsf{FPL}$

6

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

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.
Rozwiązanie (dynamiczne) przeciążenie jest na ogół NP-całkowite (Palsberg 2012). Ale w rzeczywistości rzadko stanowi to problem.
$k$
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.
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.

— xrq
źródło

1

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.

— riemann77
źródło