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

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, d$$n$$k$$l$$d$

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, d$$n$$k$$l$$d$

• , $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$
• $1\leq 2d+2-n\leq k\leq l = d< n-1$
• $k=l=d=n-1.$

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?

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

$G$$G$

Tego popołudnia czytałem Stringology - prawdziwą teorię strun .

$x$$y$$m, n$$x^m = y^n$

$m,n$$x^m = y^n$$xy = yx$

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)

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

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

$5n$$u$$v$$v$$u$$10$

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

$G$$G$

Twierdzenie o czterech kolorach upraszcza algorytm return true.

$p$

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.

$n$$n(n-1)/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.)

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.

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

$A \in M_{m \times n}$$U \in M_{m \times k}$$V \in M_{k \times n}$$A = UV$$A$

$O(r^2)$$r$

$(mn)^{O(r^2)}$$U$$V$$(mn)^{o(r)}$

Zdecydowana Diffie Hellman

$(g, g^a, g^b, g^c)$$g$$\mathbb{G}$$g^c = g^{ab}$

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

$e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$

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

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

$((V, E), s, t)$$E' \subset E$$s$$t$$(V, E')$$E'$

$s$$t$$(V, E)$$s$$t$

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

$\leq 2$$\geq 3$

$\geq 3$$K_5$$K_{3,n-3}$

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.

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.

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.