Trudno wyglądające problemy algorytmiczne ułatwiane przez twierdzenia

28

Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe) twierdzenia.

Ma to na celu zilustrowanie uczniom, że uczenie się większej liczby twierdzeń może być przydatne, nawet dla osób spoza dziedziny teorii (takich jak inżynierowie oprogramowania, inżynierowie komputerowi itp.). Oto przykład:

Pytanie: Biorąc pod uwagę liczby całkowite , czy istnieje wykres n- odwrotny (a jeśli tak, to znajdź), taki że jego łączność z wierzchołkami to k , jego łączność z krawędzią to l , a jego minimalny stopień to d ?n,k,l,dnkld

Zauważ, że wymagamy, aby parametry były dokładnie równe podanym liczbom, nie są to tylko granice. Jeśli chcesz rozwiązać to od zera, może się to wydawać dość trudne. Z drugiej strony, jeśli znasz następujące twierdzenie (patrz Ekstremalna teoria grafowa B. Bollobasa), sytuacja staje się zupełnie inna.

Twierdzenie: Niech będą liczbami całkowitymi. Istnieje wykres n- werteksów z łącznością wierzchołków k , łącznością krawędzi l i minimalnym stopniem d , tylko wtedy, gdy spełniony jest jeden z następujących warunków:n,k,l,dnkld

  • , 0kld<n/2
  • 12d+2nkl=d<n1
  • k=l=d=n1.

Warunki te są bardzo łatwe do sprawdzenia, ponieważ są prostymi nierównościami między parametrami wejściowymi, więc na pytanie o istnienie można odpowiedzieć bez wysiłku. Co więcej, dowód twierdzenia jest konstruktywny, rozwiązując również problem konstrukcyjny. Z drugiej strony wynik ten nie wydaje się wystarczająco standardowy, więc można oczekiwać, że wszyscy się o nim dowiedzą.

Czy możesz podać dalsze przykłady w tym duchu, gdzie znajomość (nie tak standardowego) twierdzenia znacznie upraszcza zadanie?

Andras Farago
źródło
1
Nie jestem pewien, czy w pełni rozumiem twoje pytania. Podany przykład to nietrywialny problem, dla którego Bollobas podał algorytm (co oznacza charakterystykę). Mam wrażenie na twoim przykładzie, że każdy nietrywialny algorytm będzie odpowiedzią ...
Bruno
3
Pierwotność i twierdzenie AKS.
Lamine
@Bruno: Mam na myśli to, że zadanie algorytmiczne staje się znacznie łatwiejsze, jeśli znasz twierdzenie, które nie jest dobrze znane, więc nikt nigdy o nim nie słyszał. Przedstawiony przykład nie jest doskonały w tym sensie, że twierdzenie to nie tylko pomaga, ale rozwiązuje problem. To, czego naprawdę szukam, to to, kiedy twierdzenie pomaga, zapewnia użyteczny skrót, ale samo w sobie nie rozwiązuje w pełni problemu.
Andras Farago
3
Wiki społeczności?
Joshua Grochow
1
Twierdzenie Robertsona-Seymoura, także przypuszczenia, które ułatwiają deterministyczne znalezienie liczb pierwszych.
Kaveh

Odpowiedzi:

31

Decydowanie o izomorfizmie prostych grup na podstawie ich tablic mnożenia. Fakt, że można tego dokonać w czasie wielomianowym wynika bezpośrednio z faktu, że wszystkie skończone proste grupy mogą być generowane przez co najwyżej 2 elementy, a obecnie jedynym znanym dowodem tego faktu jest klasyfikacja skończonych grup prostych (być może największe twierdzenie - pod względem autorów, artykułów i stron - kiedykolwiek udowodnione).

Joshua Grochow
źródło
3
To świetny przykład! BTW, komentarze do tej odpowiedzi twierdzą, że w pewnym sensie twierdzenie to jest tak trudne, jak klasyfikacja: mathoverflow.net/a/59216/35733
Sasho Nikolov
32

GG

Sasho Nikolov
źródło
9

Znajdowanie liczby (wyraźnych) rzeczywistych pierwiastków prawdziwego wielomianu, w całym ℝ lub w danym przedziale. Twierdzenie Sturma mówi, że do obliczenia liczby rzeczywistych pierwiastków wielomianu z rzeczywistymi współczynnikami można użyć sekwencji wielomianów, która spełnia niewielką liczbę wymagań.

Następnie wszystko, co musisz zrobić, to skonstruować taką sekwencję (co nie jest bardzo trudne, ale wymaga pewnych przypadków skrajnych i obsługi przypadku nierozdzielalnych wielomianów), a Bob jest twoim wujem.

Co zaskakujące, niewiele osób wie o tym wyniku, mimo że jest on dość stary (1829 r.). Jest on używany w wielu systemach algebry komputerowej, ale wszyscy profesorowie matematyki na moim uniwersytecie, o których pytałem albo wcale nie znali twierdzenia Sturma, albo znali je tylko z nazwy i że ma to coś wspólnego z pierwiastkami wielomianów.

Większość ludzi są dość zaskoczony, kiedy im powiedzieć, że coś jak liczenie rzeczywiste korzenie dokładnie jest to łatwe i nie wymaga żadnego zbliżenia, biorąc pod uwagę, że znalezienie korzeni jest znacznie trudniejsze. (Pamiętaj, że dla wielomianów stopnia ≥ 5 nie istnieje nawet „właściwa” formuła dla pierwiastków)

Manuel Eberl
źródło
9

Twierdzenie: każdy wykres płaski ma wierzchołek o stopniu co najwyżej 5.

O(n)(u,v)O(1)

5nuvvu10

Pratik Deoghare
źródło
5
Przy odrobinie staranności możesz zmniejszyć rozmiar listy przechowywanej w każdym wierzchołku do 3, a liczbę kroków sprawdzania przylegania do 6. Zobacz: Płaskie orientacje z niskim stopniem zewnętrznym i zagęszczenie macierzy przylegania. M. Chrobak i D. Eppstein. Teoria Komp. Sci. 86 (2): 243–266, 1991. ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf
David Eppstein
7

Myślę, że potomkiem tej kategorii, przynajmniej jeśli chodzi o asymetrię trudności, jest następujący problem:

GG

Twierdzenie o czterech kolorach upraszcza algorytm return true.

Jonas Kölker
źródło
5

Kolejny przykład: czy biorąc pod uwagę niekierowany wykres, ma on minimalne wycięcie, w którym wszystkie krawędzie są rozłączne? Jeśli tak, znajdź taki.

nn(n1)/2

Można go rozszerzyć na cięcia prawie minimalne, które są większe niż cięcie minimalne, ale co najwyżej o stały współczynnik. Ich liczba jest nadal ograniczona przez wielomian.

(Nie szukałem referencji, pamiętam, że te wyniki są spowodowane przez D. Karger.)

Andras Farago
źródło
4

Problem: Satifsability MSO (monadyczna logika drugiego rzędu) nad skończonymi słowami.

Twierdzenie: MSO jest równoważne skończonym automatom nad skończonymi słowami.

Powyższe można podnieść do nieskończonych słów, drzew skończonych, drzew nieskończonych.

Denis
źródło
4

Nieco bardziej skomplikowany przykład: nieujemne rozkładanie macierzy , gdy nieujemny stopień jest stały.

AMm×nUMm×kVMk×nA=UVA

O(r2)r

(mn)O(r2)UV(mn)o(r)

zotachidil
źródło
4

Zdecydowana Diffie Hellman

(g,ga,gb,gc)gGgc=gab

Przy standardowych założeniach twardości problemu z logami dyskretnymi problem ten może również wydawać się trudny.

e(g,gc)=?e(ga,gb)

e:G×GGT

Więcej informacji na ten temat można znaleźć na stronie Problem decyzyjny diffie-hellman , Boneh'98 lub w wyszukiwarce Google na temat parowania

Subhayan
źródło
3

(Trywialnie) istnienie Nash Equilibrium w skończonej grze, parzysta liczba ścieżek hamiltonowskich na sześciennym wykresie, różne rodzaje stałych punktów, przyzwoicie zrównoważone porównania w częściowych porządkach i wiele innych problemów PPAD.

Yonatan N.
źródło
Istnienie Nash Equilibrium - i wiele innych dowodów istnienia charakteryzujących PPAD - nie sprawia, że ​​którykolwiek z tych problemów jest łatwiejszy do rozwiązania algorytmicznego ...
Joshua Grochow
1
Miałem na myśli wersję decyzyjną tych problemów.
Yonatan N
2

((V,E),s,t)EEst(V,E)E

st(V,E)st

Max
źródło
1
Można powiedzieć, że przepływ jest łatwy, jeśli wiesz, że LP jest łatwe. Zatem dwa duże twierdzenia (LP w czasie wielopoziomowym i maxflow-mincut) pozwalają nam obliczyć min-cięcia.
Chandra Chekuri
@ChandraChekuri, moim osobistym odczuciem jest to, że nie do końca pasuje to pytanie: twierdzenie, że LP można rozwiązać w czasie polytime, nie pomaga nam skonstruować algorytmu dla minimalnych cięć. Potrzebujemy faktycznego algorytmu LP.
Maks.
Nie całkiem. Jeśli potrafisz efektywnie znaleźć wartość minimalnego cięcia na danym wykresie, możesz użyć takiego algorytmu do znalezienia samego cięcia.
Chandra Chekuri
2

Oto inny przykład: biorąc pod uwagę niekierowany prosty wykres, zdecyduj, czy ma dwa obwody rozłączne wierzchołków.

23

3K5K3,n3

Ponieważ łatwo jest sprawdzić, czy wykres jest jednym z wykresów dozwolonych przez Twierdzenie, zapewnia nam to algorytm wielomianowy dla problemu decyzyjnego.

Uwagi: (1) Dowód twierdzenia wcale nie jest łatwy. (2) Gdy zdecydowaliśmy, że istnieją dwa rozłączne obwody, wydaje się mniej jasne, jak rozwiązać związany z nimi problem wyszukiwania , czyli jak znaleźć takie obwody. Twierdzenie nie daje na to bezpośredniej rady.

Andras Farago
źródło
1

mniej złożone przykłady: istnieją pewne właściwości podobne do twierdzeń, które pokazują, że zachłanne algorytmy dla niektórych problemów są optymalne. nie jest to tak oczywiste dla niewtajemniczonych, że chciwy algorytm może znaleźć minimalne drzewo rozpinające . nieco podobnym koncepcyjnie jest algorytm Dijkstry znajdujący najkrótszą ścieżkę na wykresie. w obu przypadkach powiązane „twierdzenia” są prawie takie same jak algorytmy.

vzn
źródło
Myślę, że będzie to lepsza odpowiedź, jeśli na przykład załączysz stwierdzenie właściwości cut MST i wspomnisz, jak implikuje to poprawność całej klasy zachłannych algorytmów MST.
Sasho Nikolov
MST wycięte nieruchomości wymienione na stronie wikipedia str. może możesz odwołać się do innych uogólnień, które tam nie zostały omówione przy okazji przypomnijmy, że pytający poprosił o przykłady służące „osobom spoza pola teorii” (inne fajne przykłady mogą być zbyt zaawansowane dla osób postronnych)
vzn
TeTeABeE(A,B)
1

Znajdź sekwencję liczb Fibonacciego, które są iloczynem innych liczb Fibonacciego. Na przykład liczba Fibonacciego 8 znajduje się w sekwencji, ponieważ 8 = 2 * 2 * 2, a 2 to liczba Fibonacciego, która nie jest równa 8. Liczba Fibonacciego 144 znajduje się w sekwencji, ponieważ 144 = 3 * 3 * 2 * 2 * 2 * 2, a zarówno 2, jak i 3 są liczbami Fibonacciego, które nie są równe 144.

Twierdzenie Carmichaela sugeruje, że 8 i 144 są jedynymi terminami tej sekwencji.

Bob Lyons
źródło