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

29

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ą)?

Anton Menshov
źródło
2
Przychodzi na myśl przekleństwo wymiarowości.
Paweł
4
wykres 2-kolorowanie ( łatwe ) w porównaniu do 3-kolorowanie ( NP-twarde ), patrz tutaj
GoHokies
5
@ GoHokies Proszę nie zamieszczać odpowiedzi jako komentarzy.
David Richerby
4
Od podstaw matematyki lub tła rekurencyjnego możesz natknąć się na funkcję DRZEWO , gdzie DRZEWO (2) = 3, a DRZEWO (3) jest ... dość duże. (nie jestem zaznajomiony z naukami obliczeniowymi, nie jestem pewien, czy naprawdę jest to odpowiedź, której szukasz, ale wydaje się wystarczająco podobny, aby zostawić komentarz)
BurnsBA
2
Kontrprzykład: „Nigdy nie idź na morze z dwoma chronometrami; weź jeden lub trzy”. To powiedziawszy, istnieje tyle dobrych przykładów, że nie ma właściwej odpowiedzi. To pytanie powinno być wiki społeczności.
David Hammen

Odpowiedzi:

35

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 .

davidhigh
źródło
3
Nitpick, którego na pewno znasz, ale twoja odpowiedź nie mówi: istnieją zamknięte rozwiązania problemu 3 ciał, ale tylko w kilku szczególnych przypadkach
lama
dobry nitpick, dzięki, brakuje tutaj „ogólnie”.
davidhigh
Zauważ, że problem z trzema ciałami ma ( bardzo powoli zbieżne) rozwiązanie szeregowe znalezione przez Sundmana na początku XX wieku i słabszą wersję (która ignoruje osobliwości, w których zderzają się ciała) znaleziono dla problemu n-ciała w 1990 roku.
WorldSEnder
27

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.

Federico Poloni
źródło
3
3-SAT można zredukować do kolorowania na wykresie 3 lub odwrotnie
GoHokies
8
@ GoHokies Myślałem, że to prawda w przypadku każdego problemu np. Kompletnego? Czy jest coś szczególnie godnego uwagi w tych dwóch przypadkach? Jeśli to głupie pytanie, moja wiedza na ten temat jest podstawowa. Ale tak rozumiem twierdzenie o kucharzach
findusl
2
@findusl Masz całkowitą rację. To, co wyróżnia 3-SAT i 3-kolorowanie jako „wyjątkowe”, to dychotomia OP 2-w-3.
GoHokies
26

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 .

Mark L. Stone
źródło
21

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 .

Richard Zhang
źródło
20

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

ajd
źródło
11

A1A2

U1TA1V=Σ1,U2TA2V=Σ2

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

QTA1Z=A1~,QTA2Z=A2~,QTA3Z=A3~

(A1+λA2+λ2A3)x=0

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

Anton Menshov
źródło
U1TU2TV1
1
Σ
9

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(uavbwcTabc/uvw)

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

Dan Stahlke
źródło
2
Wydaje mi się, że prawdziwym problemem jest to, że rozkład rang tensora jest łatwy dla tensorów rzędu 1 (wektory) i tensorów rzędu 2 (macierze), ale dla pozostałych trudnych NP
Richard Zhang
To część tego, ale nawet jeśli potrafisz je rozłożyć, nadal istnieje problem kategoryzacji / klasyfikacji. W przypadku splątania lokalne jednostki unitarne nie mają znaczenia, więc wszystko, co pozostało w przypadku rzędu 2, to lista pojedynczych wartości (w tym kontekście SVD nazywa się rozkładem Schmidta). Dla wyższych zamówień jest całe zoo możliwości. Pytania, takie jak które stany można przekształcić w inne stany za pomocą operacji lokalnych, stają się bardzo trudne (z teoretycznego punktu widzenia, niekoniecznie obliczeniowe).
Dan Stahlke
5

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

davidhigh
źródło
4

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.

André Popovitch
źródło
4

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:

minf1(x1)+f2(x2)
s.t.A1x1+A2x2=b

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

Lρ(x1,x2,λ)=f1(x1)+f2(x2)+λT(A1x1+A2x2b)+ρ2||A1x1+A2x2b||22

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ρ(x1,x2,λ)x1x2,λLρ(x1,x2,λ)x2x1,λλ

(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

minf1(x1)+f2(x2)+f3(x3)
s.t.A1x1+A2x2+A3x3=b

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.fxiλ

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

Nathaniel Kroeger
źródło
3

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.

Toczeń Arcanist
źródło
3
Twój pierwszy przykład nie pasuje do ducha cytatu. Chodzi o to, że gdy robi się wyżej po drugiej, jest trudniej, ale przy składaniu papieru czwarty jest prawie tak łatwy jak połowa. Cytat tutaj brzmiałby: „Parzyste jest łatwiejsze niż dziwne”. Myślę, że drugi jest dobry - i „gratuluję hiper-uproszczenia go za pomocą papieru!
Bill K
3

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)=0f

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.f(x)ff
  • 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.
doetoe
źródło
1

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.

justhalf
źródło
TREE(3)jest „obliczalny”, biorąc pod uwagę wystarczającą ilość czasu. Na przykład dla każdego można wygenerować wszystkie kolorowe drzewa o rozmiarze i sprawdzić, czy każde spełnia niezbędne kryteria, dopóki takie drzewa nie istnieją. Ale zajęłoby to niewyobrażalną ilość miejsca i czasu. nn
Przywróć Monikę
Tak, przepraszam za błąd. Naprawiono moje oświadczenie. Dzięki Solomonoff!
justhalf
1
Powiązany film numeryczny o drzewie (3): youtube.com/watch?v=3P6DWAwwViU
nowicjusz C
1

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.

Patrick Sanan
źródło
0

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

Albert B.
źródło
-3

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

Joelty
źródło
2
Czy możesz podać odniesienia do swoich roszczeń?
nicoguaro
Nie mogę, ale spójrzmy na np. Samochody samobieżne. Nauka jazdy samochodem na prostej i kontrolowania prędkości jest prawdopodobnie łatwiejsza niż nauka jazdy jak normalna osoba. Im bardziej złożony proces, tym więcej przypadków granicznych pojawia się, gdy chcesz go w pełni zautomatyzować
Joelty
Myślę zatem, że twoje pytanie nie jest odpowiednie dla tej witryny.
nicoguaro