Czy istnieją dowody istnienia niekonstruktywnego algorytmu?

Pamiętam, że mogłem spotkać odniesienia do problemów, które zostały udowodnione, że można je rozwiązać ze szczególną złożonością, ale bez znanego algorytmu, który by faktycznie osiągnął tę złożoność.

Walczę z tym, jak to się dzieje; jak wyglądałby niekonstruktywny dowód na istnienie algorytmu.

Czy rzeczywiście istnieją takie problemy? Czy mają dużą wartość praktyczną?

Rozważ funkcję (wziętą stąd )

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Pomimo wyglądu, można obliczyć na podstawie następującego argumentu. Zarówno$f$

1. $0^n$ występuje dla każdego lub$n$
2. jest $k$ więc $0^k$ występuje, ale $0^{k+1}$ nie.

Nie wiemy, co to jest (jeszcze), ale wiemy, że z$f \in F = \{f_\infty, f_0, f_1, \dots \}$

1. i$f_\infty(n) = 1$
2. .$f_k(n) = [n \leq k]$

Ponieważ , f jest obliczalne - ale nie możemy powiedzieć, czym jest f .$F \subset \mathsf{RE}$$f$$f$

To może nie być dokładnie to , co masz na myśli, ale optymalny algorytm minimalnego drzewa opinającego Seth Pettie i Vijaya Ramachandran jest w pewnym sensie niekonstruktywny.

Pozostaje otwarte pytanie, czy istnieje algorytm deterministyczny do obliczania minimalnego drzewa rozpinającego w czasie liniowym (czyli ). Pettie i Ramachandran opisują algorytm obliczający MST w czasie liniowym, jeśli taki algorytm istnieje .$O(n+m)$

Intuicyjnie, algorytm zmniejsza ich dowolną wystąpienie -Vertex problemu MST do O ( n / k ) mniejsze instancje O ( k ) wierzchołków liniowego czasu, gdzie (powiedzmy) K = O ( log log log log log log log n ) . Następnie obliczają optymalne drzewo porównania, które oblicza minimalne drzewo rozpinające dowolnego wykresu k -vertex poprzez wyliczenie siły brutalnej; nawet jeśli zajmuje to pięciokrotnie wykładniczy czas wk , to tylko $n$$O(n/k)$$O(k)$$k = O(\log\log\log\log\log\log\log n)$$k$$k$ czas. Wreszcie rozwiązują małe wystąpienia za pomocą tego optymalnego drzewa decyzyjnego.$O(\log\log n)$

Innymi słowy, Pettie i Ramachandran konstruują optymalny algorytm MST tylko pośrednio, konstruując algorytm, który konstruuje optymalny algorytm MST.

Oto dwa przykłady.

1. Niektóre algorytmy wykorzystujące twierdzenie Robertsona-Seymour'a . Twierdzenie mówi, że dla każdego przypadku wychodzi skończona przeszkoda, ale nie zapewnia sposobu na znalezienie takiego zbioru skończonego. Dlatego, chociaż możemy udowodnić, że algorytm istnieje, wyraźne określenie algorytmu będzie zależeć od skończonego zestawu przeszkód, którego nie umiemy znaleźć. Innymi słowy, wiemy, że istnieje algorytm, ale nie wiemy (jeszcze) jak go znaleźć.

2. Silniejszym przykładem, chociaż mniej naturalnym, jest zasadniczo stosowanie PEM lub podobnych niekonstruktywnych aksjomatów. Jest to silniejsze w tym sensie, że możemy udowodnić, że konstruktywne istnienie algorytmu oznaczałoby niekonstruktywny aksjomat (podobny do słabych kontrprzykładów Brouwera ). Taki przykład jest silniejszy, ponieważ nie tylko mówi, że obecnie nie znamy żadnego wyraźnego algorytmu (ani żadnego algorytmicznego sposobu jego znalezienia), ale także że nie ma na to nadziei.

   Jako przykład możemy użyć PEM, aby udowodnić istnienie algorytmu, podczas gdy nie wiemy, który z nich i konstruktywny sposób znalezienia takiego oznaczałoby niekonstruktywny aksjomat. Podam prosty przykład:

   Problem zatrzymania jest trywialnie rozstrzygalny dla każdej stałej maszyny Turinga (każda TM zatrzymuje się lub nie zatrzymuje się, aw każdym przypadku jest TM, która daje prawidłową odpowiedź), ale jak znaleźć algorytm rozwiązujący problem poprawnie bez rozwiązania ( jednolita wersja) problemu zatrzymania?

   Bardziej formalnie, nie możemy udowodnić, że dali konstruktywnie TM , istnieje TM H T decyduje wstrzymaniem problem dla M . Bardziej formalnie, następujące stwierdzenie nie może zostać udowodnione konstruktywnie:$M$$H_T$$M$

   $$\forall e\in \mathbb{N} \ \exists f\in \mathbb{N} \ \left[ (\{f\}( \ )=0 \land \{e\}\mathord{\downarrow}) \lor (\{f\}( \ )=1 \land \{e\}\mathord{\uparrow}) \right]$$

   Tutaj jest TM z kodem e (w niektórych stałych reprezentacjach TM), { e } ↓ oznacza { e } zatrzymuje się, a { f } ↑ oznacza { f } nie zatrzymuje się.$\{e\}$$e$$\{e\}\mathord{\downarrow}$$\{e\}$$\{f\}\mathord{\uparrow}$$\{f\}$

Tak.

W jednym punkcie (1), twierdzenie o dychotomii złożonego ważenia wykresu homomorfizmu dla dowolnej skończonej wielkości domeny, Cai, Chen i Lu, tylko dowodzi istnienia redukcji czasu wielomianowego między dwoma problemami liczenia poprzez interpolację wielomianową. Nie znam żadnej praktycznej wartości takiego algorytmu.

Zobacz rozdział 4 wersji arXiv. Lemat, o którym mowa, to Lemma 4.1, zwana „Pierwszą lemią przypinającą”.

Jednym ze sposobów, aby ten dowód był konstruktywny, jest udowodnienie złożonej wersji wyniku Lovasz , a mianowicie:

Dla wszystkich , Z H ( G , wagowo , I ) = Z H ( G , W , j ) iff istnieje automorfizmem F z G , tak że F ( I ) = j .$G$$Z_H(G, w, i) = Z_H(G, w, j)$$f$$G$$f(i) = j$

Tutaj to wierzchołek w H , I i J są wierzchołki G i Z H ( G , W , i ) jest sumą na wszystkich złożonych ważonych homomorfizmów wykres z G do H, z tym ograniczeniem, że , że muszą być odwzorowane do w .$w$$H$$i$$j$$G$$Z_H(G, w, i)$$G$$H$$i$$w$

(1) Jin-Yi Cai, Xi Chen i Pinyan Lu, Wykres Homomorfizmy ze złożonymi wartościami: twierdzenie o dychotomii ( arXiv ) ( ICALP 2010 )

Niektóre wczesne wyniki z późnych lat 80-tych:

• Fellows i Langston, „ Niekonstruktywne narzędzia do udowadniania rozstrzygalności w czasie wielomianowym ”, 1988

• Brown, Fellows, Langston, „ Samoodwracalność w czasie wielomianowym: motywacje teoretyczne i praktyczne wyniki ”, 1989

Z streszczenia drugiego przedmiotu:

Ostatnie zasadnicze postępy w teorii grafów umożliwiły jednak udostępnienie nowych, niekonstruktywnych narzędzi, które można zastosować w celu zagwarantowania członkostwa w P. Narzędzia te nie są konstruktywne na dwóch różnych poziomach: nie wytwarzają algorytmu decyzyjnego, ustalając jedynie skończoność zestawu przeszkód , ani nie ujawniają, czy taki algorytm decyzyjny może być pomocny w budowie rozwiązania. Przeglądamy krótko i ilustrujemy użycie tych narzędzi oraz omawiamy pozornie ogromne zadanie znalezienia obiecanych algorytmów decyzji w czasie wielomianowym, kiedy te nowe narzędzia będą miały zastosowanie.

Przykład nieskończonej rodziny problemów (o wątpliwej wartości praktycznej), dla których możemy pokazać:

1. Że dla każdego problemu istnieje algorytm do jego rozwiązania.
2. Że nie ma sposobu na zbudowanie tych algorytmów (ogólnie).

Innymi słowy, dowód, który można udowodnić, nie jest konstruktywny. Nasza rodzina problemów (z tego pytania ) dla każdej maszyny Turinga :$M$

$L_{M}=\Bigl\{\langle M'\rangle \;\Big|\;\; L(M)=L(M') \text{ and } |\langle M\rangle| \geq | \langle M' \rangle| \Bigr\}$

1. $M$

2. $P$$M$$P(\langle M \rangle)$$L_M$$M$$M'$$|\langle M \rangle | \geq |\langle M' \rangle|$$P(\langle M \rangle)(\langle M' \rangle)$$P$

Z „Notek z teorii dwuwymiarowości i wykresów algorytmicznych - drobne wykłady” do samouczka Mohammada Taghi Hajiaghayiego autorstwa Mareike Massow, Jensa Schmidta, Darii Schymury i Siamaka Tazari.

Każda drobna właściwość zamkniętego wykresu może być scharakteryzowana przez skończony zestaw zabronionych nieletnich.

Niestety ich wynik jest „z natury” niekonstruktywny, tzn. Nie ma algorytmu, który mógłby ogólnie określić, które nieletnie mają być wykluczone dla danej właściwości niewielkiego zamkniętego wykresu. Ponadto liczba niedozwolonych nieletnich może być wysoka: na przykład w przypadku wykresów umieszczanych na torusie znanych jest ponad 30 000 niedozwolonych nieletnich, ale lista jest niepełna.

[...]

Każda drobna właściwość zamkniętego wykresu może być ustalana w czasie wielomianowym (nawet w czasie sześciennym).

Algorytmiczny lokalny lemat Lovásza - „Algorytmiczny lokalny lemat Lovásza daje algorytmiczny sposób konstruowania obiektów, które są zgodne z systemem ograniczeń o ograniczonej zależności. ... Jednak lemat nie jest konstruktywny, ponieważ nie daje żadnego wglądu w to, jak aby uniknąć złych wydarzeń ”. Przy niektórych założeniach / ograniczeniach dystrybucji, Moser / Tardos podaje skonstruowany algorytm [1]. lemat lokalny Lovasz wydaje się mieć różne głębokie powiązania z teorią złożoności, np. patrz [2]

[1] Konstruktywny dowód generała Lovásza Local Lemma autorstwa Mosera, Tardosa

[2] Lov´asz Local Lemma and Satisfiable Gebauer, Moser, Scheder, Welzl