Dobre przykłady „dwa są łatwe, trzy są trudne” w naukach obliczeniowych

Ostatnio spotkałem się z sformułowaniem meta-zjawiska : „ dwa są łatwe, trzy są trudne ” (sformułowane w ten sposób przez Federico Poloni), które można opisać następująco:

Kiedy sformułowany jest pewien problem dla dwóch podmiotów, jest on stosunkowo łatwy do rozwiązania; jednak algorytm formułowania trzech podmiotów ogromnie zwiększa trudność, być może nawet czyniąc rozwiązanie niemożliwym lub nieosiągalnym.

_{(Z zadowoleniem przyjmuję sugestie, aby sformułowanie było piękniejsze, zwięzłe i dokładne).}

Jakie znasz dobre przykłady z różnych dziedzin nauk obliczeniowych (od czystej algebry liniowej po ogólną fizykę obliczeniową)?

Jednym z przykładów, który pojawia się w wielu obszarach fizyki, a zwłaszcza w mechanice klasycznej i fizyce kwantowej, jest problem dwóch ciał. Problem dwóch ciał oznacza tutaj zadanie obliczenia dynamiki dwóch oddziałujących cząstek, które na przykład oddziałują siłami grawitacyjnymi lub kulombowskimi. Rozwiązanie tego problemu często można znaleźć w formie zamkniętej przez zmienną transformację w środek masy i współrzędne względne.

Jednak gdy tylko weźmie się pod uwagę trzy cząstki, na ogół nie ma rozwiązań w formie zamkniętej .

Znanym przykładem jest boolowski problem satysfakcji (SAT). 2-SAT nie jest skomplikowany do rozwiązania w czasie wielomianowym, ale 3-SAT jest NP-kompletny.

W jednym i dwóch wymiarach wszystkie drogi prowadzą do Rzymu, ale nie w trzech wymiarach.

Konkretnie, biorąc pod uwagę losowy spacer (równie prawdopodobne, że porusza się w dowolnym kierunku) na liczbach całkowitych w jednym lub dwóch wymiarach, to bez względu na punkt początkowy, z prawdopodobieństwem jeden (czyli prawie na pewno), losowy spacer ostatecznie dojdzie do określonego wyznaczonego punkt („Rzym”).

Jednak w przypadku trzech lub więcej wymiarów prawdopodobieństwo dotarcia do „Rzymu” jest mniejsze niż jeden; prawdopodobieństwo maleje wraz ze wzrostem liczby wymiarów.

Na przykład, jeśli przeprowadzimy stochastyczną (Monte Carlo) symulację losowego spaceru rozpoczynającego się w „Rzymie”, który zatrzyma się po powrocie Rzymu, to w jednym i dwóch wymiarach możesz mieć pewność, że w końcu wrócisz do Rzymu i zatrzymanie symulacji - takie proste. W trzech wymiarach nigdy nie będzie tak ciężko.

https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

Aby zwizualizować dwuwymiarową obudowę, można sobie wyobrazić osobę chodzącą losowo po mieście. Miasto jest faktycznie nieskończone i ułożone w kwadratową siatkę chodników. Na każdym skrzyżowaniu osoba losowo wybiera jedną z czterech możliwych tras (w tym tę, z której pierwotnie podróżował). Formalnie jest to losowy spacer po zbiorze wszystkich punktów na płaszczyźnie o współrzędnych całkowitych.

Czy dana osoba kiedykolwiek wróci do pierwotnego punktu początkowego spaceru? Jest to dwuwymiarowy odpowiednik problemu przekraczania poziomu omówionego powyżej. W 1921 roku George Pólya udowodnił, że osoba prawie na pewno poszedłaby w dwuwymiarowy losowy spacer, ale dla 3 lub więcej wymiarów prawdopodobieństwo powrotu do źródła maleje wraz ze wzrostem liczby wymiarów. W 3 wymiarach prawdopodobieństwo spada do około 34%

Wartości liczbowe można znaleźć na stronie http://mathworld.wolfram.com/PolyasRandomWalkConstants.html .

Oto jedno bliskie sercom autorów SciComp.SE:

Istnienie Naviera-Stokesa i gładkość problemem

Trójwymiarowa wersja jest oczywiście znanym otwartym problemem i przedmiotem nagrody Clay Millenium za milion dolarów. Ale dwuwymiarowa wersja została już dawno rozwiązana, z twierdzącą odpowiedzią. Terry Tao zauważa, że rozwiązanie pochodzi zasadniczo z tezy Leraya w 1933 roku!

Dlaczego problem trójwymiarowy jest o wiele trudniejszy do rozwiązania? Standardowa reakcja na falowanie ręczne polega na tym, że turbulencje stają się znacznie bardziej niestabilne w trzech wymiarach niż w dwóch. Aby uzyskać bardziej matematycznie rygorystyczną odpowiedź, sprawdź oficjalne oświadczenie Charlesa Feffermana w Clay Institute lub miłą prezentację Terry Tao na temat możliwych strategii dowodowych .

W teorii wyboru społecznego zaprojektowanie schematu wyborczego z dwoma kandydatami jest łatwe (reguły większości), ale zaprojektowanie schematu wyborczego z trzema lub więcej kandydatami koniecznie wymaga dokonania kompromisu między różnymi rozsądnie brzmiącymi warunkami. ( Twierdzenie o niemożliwości Arrow ).

$A_1$$A_2$

Jednak gdy wymagane jest równoczesne zredukowanie trzech macierzy do postaci kanonicznej (stan słabszy w porównaniu do powyższego):

Źródło: CF van Loan, „Wykład 6: Uogólniony rozkład wartości pojedynczej wyższego rzędu”, CIME-EMS Summer School, Cetraro, Włochy, czerwiec 2015 r.

Istnieje wiele przykładów w obliczeniach kwantowych, chociaż od jakiegoś czasu jestem z tego powodu, więc nie pamiętam wielu. Jednym z głównych jest to, że dwustronne splątanie (splątanie między dwoma systemami) jest względnie łatwe, podczas gdy splątanie między trzema lub więcej systemami jest nierozwiązanym bałaganem z prawdopodobnie setką artykułów na ten temat.

$\max\left(u_a v_b w_c T^{abc} / \left\lVert u \right\rVert \left\lVert v \right\rVert \left\lVert w \right\rVert \right)$

Ten artykuł wydaje się trafny, chociaż go nie przeczytałem: większość problemów z tensorem jest trudna do NP

Bisekcja kąta za pomocą linii prostej i kompasu jest prosta, a przecięcie kąta jest zasadniczo niemożliwe.

Wnioskowanie o typach dla typów Rank-n . Wnioskowanie typu dla rangi 2 nie jest szczególnie trudne, ale wnioskowanie typu dla rangi 3 lub wyższej jest nierozstrzygalne.

Oto schludny z optymalizacji: algorytm Alternative Direction Method of Multipliers (ADMM).

Biorąc pod uwagę niesprzężoną i wypukłą funkcję celu dwóch zmiennych (same zmienne mogą być wektorami) oraz ograniczenie liniowe łączące dwie zmienne:

Rozszerzoną funkcją Lagrangian dla tego problemu optymalizacji byłby wtedy

Algorytm ADMM z grubsza działa, wykonując podział „Gaussa-Seidela” na rozszerzonej funkcji Lagrangiana dla tego problemu optymalizacji, minimalizując najpierw w odniesieniu do (podczas gdy pozostają naprawiono), następnie minimalizując w odniesieniu do (podczas gdy pozostają stałe), a następnie aktualizując . Cykl ten trwa do momentu spełnienia kryterium zatrzymania.$L_{\rho}(x_1, x_2, \lambda)$$x_1$$x_2, \lambda$$L_{\rho}(x_1, x_2, \lambda)$$x_2$$x_1, \lambda$$\lambda$

(Uwaga: niektórzy badacze, tacy jak Eckstein, odrzucają widok podziału Gaussa-Siedela na rzecz operatorów proksymalnych, na przykład patrz http://rutcor.rutgers.edu/pub/rrr/reports2012/32_2012.pdf )

W przypadku problemów wypukłych udowodniono, że algorytm ten jest zbieżny - dla dwóch zestawów zmiennych. Nie dotyczy to trzech zmiennych. Na przykład problem optymalizacji

Nawet jeśli wszystkie są wypukłe, podejście podobne do ADMM (minimalizowanie rozszerzonego Lagrangiana w odniesieniu do każdej zmiennej , a następnie aktualizowanie podwójnej zmiennej ) NIE jest gwarantowane, aby się zbiegało, jak pokazano w tym artykule.$f$$x_i$$\lambda$

https://web.stanford.edu/~yyye/ADMM-final.pdf

Złożenie kartki papieru na pół bez użycia narzędzi jest łatwe. Składanie go na trzy części jest trudne.

Faktoring wielomianu z dwoma pierwiastkami jest łatwy. Faktoring wielomianu z trzema pierwiastkami jest znacznie bardziej skomplikowany.

Gładka krzywa stopnia 2 (tzn. Podana jako rozwiązanie gdzie jest wielomianem stopnia 2) z danym punktem jest racjonalna , co oznacza, że ​​można ją sparametryzować za pomocą ilorazów wielomianów stopnia 3 to nie jest. Te pierwsze są uważane za dobrze zrozumiałe, te drugie, zwane krzywymi eliptycznymi, gdy punkt bazowy, czyli konkretne rozwiązanie, jest wyszczególnione, są przedmiotem intensywnych badań.$f(x,y) = 0$$f$

Ta różnica ma kilka implikacji:

• W stopniu 2 istnieją algorytmy do znalezienia wszystkich punktów wymiernych (rozwiązania w liczbach wymiernych), w stopniu 3 taki algorytm nie jest znany.
• Całki obejmujące z stopnia 1 i 2 mają rozwiązania funkcji elementarnych, ale nie dla stopnia 3 lub wyższego.$\sqrt{f(x)}$$f$$f$
• Problem z dyskretnym logarytmem można rozwiązać na krzywych stopnia 2, a zatem nie nadaje się do zastosowań kryptograficznych, podczas gdy założona twardość tego samego problemu na krzywych eliptycznych leży u podstaw niektórych najpopularniejszych kryptosystemów klucza publicznego.

TREEFunkcja.

Możemy obliczyć TREE(2) = 3, ale TREE(3)nie da się go obliczyć w czasie życia wszechświata, wiemy tylko, że jest on skończony.

W przestrzeni dwuwymiarowej można wprowadzić złożoną strukturę, która może być wykorzystana do eleganckiego rozwiązania wielu problemów (np. Potencjalnych problemów z przepływem ), ale analog nie istnieje w 3 wymiarach.

W kwantowej fizyce wielu ciał badamy różne sieci n spinów w ramach różnych modeli (np. Model Heisenberga, model Bosego-Hubbarda, model Isinga, ...). Masz oczywiście różne metody numeryczne do ich badania (DMRG, dokładna diagonalizacja, sieci neuronowe, ...), a jednym z powodów, dla których próbujemy opracować różne metody, jest to, że nie możesz rozwiązać tych modeli, gdy n staje się zbyt „wysoki” , i oczywiście jest gorzej, jeśli uczysz się w wyższych wymiarach. Na przykład dla modelu Isinga dokładna diagonalizacja działa dobrze w 1d dla n nie wyższej niż 20. Tak więc, dla wyższego n, wypróbowujesz inną metodę: DMRG. Ale te ostatnie działają naprawdę dobrze dla wyższych n (jak n = 70, ale nie dobrze dla wyższych n). Ponownie, potrzebujesz innej metody dla wyższych n: sieci neuronowych (tj. Sztucznej inteligencji). Oprócz sieci neuronowych możesz uczyć się „łatwiej” (tj. z relatywnie wyższym n) tymi modelami w wyższych wymiarach (ale dla wymiaru = 3 i małego n, na przykład, nadal zajmuje dużo godzin (kilka dni), aby uzyskać stan podstawowy lub zauważalne, że chciałeś ...). Bref, kiedy n staje się „zbyt wysoki” dla twoich metod numerycznych (ale także pojemności twojego komputera) musisz wykonać nowe metody (i jeśli możesz, użyj superkomputera) i jest to ten sam problem z rozmiarem twojego system, ale gorzej oczywiście, ponieważ szybko utkniesz (wymiar = 4 jest trudny do uzyskania, chyba że czekasz dużo czasu ...). uzyskanie stanu podstawowego lub możliwego do zaobserwowania pożądanego stanu zajmuje jeszcze wiele godzin (kilka dni)). Bref, kiedy n staje się „zbyt wysoki” dla twoich metod numerycznych (ale także pojemności twojego komputera) musisz wykonać nowe metody (i jeśli możesz, użyj superkomputera) i jest to ten sam problem z rozmiarem twojego system, ale gorzej oczywiście, ponieważ szybko utkniesz (wymiar = 4 jest trudny do uzyskania, chyba że czekasz dużo czasu ...). uzyskanie stanu podstawowego lub możliwego do zaobserwowania pożądanego stanu zajmuje jeszcze wiele godzin (kilka dni)). Bref, kiedy n staje się „zbyt wysoki” dla twoich metod numerycznych (ale także pojemności twojego komputera) musisz wykonać nowe metody (i jeśli możesz, użyj superkomputera) i jest to ten sam problem z rozmiarem twojego system, ale gorzej oczywiście, ponieważ szybko utkniesz (wymiar = 4 jest trudny do uzyskania, chyba że czekasz dużo czasu ...).
Oczywiście, tutaj są bardziej dodatkowe informacje do twojego pytania, ponieważ tak naprawdę, w kwantowej fizyce wielu ciał, n = 3 nie jest wysokie (ale jeśli weźmiesz kratkę, która jest hipersześcianem, nie możesz wziąć n = 3 z kurs (z powodu warunków)).

Prawdziwy świat:

Automatyzacja% - np. Łatwo jest zautomatyzować coś w 30%, 50% lub 80%, tymczasem trudno jest przekroczyć np. 95% i niewiarygodnie trudno lub nawet prawie niemożliwe jest osiągnięcie 100%.