Skuteczne uniwersalne narzędzie do rozwiązywania problemów?

Zdefiniuj „problem” jako algorytm akceptujący liczbę naturalną i zwracający 0 lub 1, która zwraca na co najmniej jednym . Każde takie nazywane jest „rozwiązaniem” $A$ $1$ $n \in \mathbb{N}$ $n$ $A$

Zdefiniuj „uniwersalne narzędzie do rozwiązywania problemów” jako algorytm przyjmujący problem i zwracający jedno z jego rozwiązań. Na przykład może działać, zapętlając wszystkie liczby naturalne i uruchamiając na nich swoje dane wejściowe, aż do uzyskania wyników (musi zatrzymać się tylko na poprawnych danych wejściowych) $U$ $U$ $1$

Jestem zainteresowany badaniem granic wydajności w uniwersalnych rozwiązaniach problemów

Biorąc pod uwagę, że jest uniwersalnym rozwiązaniem problemu, a problemem, oznacz czas, jaki zajmuje wytworzenie wyniku po zaakceptowaniu wejścia $U$ $A$ $t(U, A)$ $U$ $A$

Uniwersalne narzędzie do rozwiązywania problemów jest nazywane „wydajnym”, gdy mamy do czynienia z dowolnym uniwersalnym narzędziem do rozwiązywania problemów $U$ $V$

t (U, A) < t (V, A) + t_{V}

$t(U, A) < t(V, A) + t_V$

Tutaj zależy od ale nie zależy od $t_V$ $V$ $A$

Czy istnieją skuteczne uniwersalne narzędzia do rozwiązywania problemów?

EDYCJA: Zdałem sobie sprawę, że można zmienić definicje „problemu” i „uniwersalnego rozwiązania problemu” na coś nieco bardziej eleganckiego i zasadniczo równoważnego. „Problem” to algorytm bez danych wejściowych zwracający 0 lub 1 (który zatrzymuje się). „Uniwersalny program rozwiązywania problemów” to algorytm przyjmujący problem i zwracający jego wynik. To mniej więcej uniwersalna maszyna Turinga

Starą definicję można sprowadzić do nowej definicji, ponieważ biorąc pod uwagę problem w starym znaczeniu, możemy skonstruować problem w nowym znaczeniu, który po prostu stosuje trywialny uniwersalny rozwiązywanie problemów starego do (solver opisany w powyższym tekście ) $A$ $B$ $A$

Nową definicję można sprowadzić do starej definicji, ponieważ biorąc pod uwagę problem w nowym znaczeniu, możemy skonstruować problem w starym znaczeniu, który po prostu oblicza i porównuje dane wejściowe z wynikiem $B$ $A$ $B$

Trywialnym przykładem uniwersalnego narzędzia rozwiązywania problemów w nowym sensie jest algorytm, który po prostu uruchamia dane wejściowe

cc.complexity-theory ai.artificial-intel Vanessa
źródło

Odpowiedzi:

Nie ma skutecznego uniwersalnego rozwiązania problemu. Intuicyjnie, U powinien mieć (prawie) optymalny czas działania dla każdego rozstrzygającego problemu decyzyjnego; podczas gdy twierdzenie o przyspieszeniu mówi, że istnieją rozstrzygalne problemy decyzyjne, które nie mają optymalnego algorytmu (nawet w bardzo łagodnym sensie). Aby sformalizować to:

Twierdzenie o przyspieszeniu czasu (patrz na przykład [1])): Dla każdej obliczalnej (i ) funkcji istnieje zbiór rozstrzygalny taki, że jeśli to dla spełniające . $g$ $S$ $S \in DTIME(t)$ $S \in DTIME(t')$ $t'$ $g(t'(n)) < t(n)$

Poniżej pracujemy z drugą definicją. Niech będzie uniwersalnym rozwiązaniem problemu. Niech i jest algorytmem, który decyduje . Niech będzie TM bez wejścia st . Istnieje TM z około logarytmicznym przeciążeniem w czasie wykonywania (kodowanie i różni się tylko ). Przy tym przyspieszeniu istnieje TM która decyduje o i . Mamy więc . $U$ $g(n)=2^{2n}$ $A$ $S$ $A_i$ $A_i = A(i)$ $\tilde U(i)=U(A_i)$ $A$ $A_i$ $O(\log i)$ $B$ $S$ $2^{ 2 TIME(B)} < TIME(\tilde U)$ $2^{TIME(B)} < TIME(\{U(A_i)\})$

Niech będzie uniwersalnym rozwiązaniem problemu, takim jak dla wejścia , symuluje on z logarytmicznym przeciążeniem w czasie. (Oczywiście funkcje wykonawcze zarówno i są nieograniczone) Tak więc mamy $V$ $A_i$ $B(i)$ $A(i)$ $B(i)$

$\forall c \; \exists A_i \;\; t(U, A_i) > t(V, A_i) +c$

Więc nie może być wydajny. $U$

[1] Oded Goldreich, Złożoność obliczeniowa, Perspektywa konceptualna, twierdzenie 4.8. Istotny jest również rozdział 4.2.1.2.

Ruhollah Majdoddin
źródło

Świetne rozwiązanie, dzięki!

Vanessa,

Uniwersalny algorytm Levina to taki algorytm, że . Zmieniając algorytm (patrz na przykład najszybszy i najkrótszy algorytm Huttera dla wszystkich dobrze zdefiniowanych problemów ), możesz uczynić uniwersalną stałą, choć zdecydowanie nie jak potrzebujesz. W przypadku prac pokrewnych zapoznaj się z pracą Hirscha, Itsyksona i ich uczniów, na przykład ten raport techniczny . $t(U,A) < s_V t(V,A) + t_V$ $s_V$ $1$

Edycja: Jak komentuje Squark, czas działania algorytmu Levina zależy również od czasu działania , ponieważ musi on zweryfikować swoje odpowiedzi. Aby uzyskać stałą $A$ $s_V$

Yuval Filmus
źródło

U

$U$

s_{V}

$s_V$

V

$V$

s_{V}

$s_V$

t_{V}

$t_V$

V

$V$

Nie rozumiem jak. Przy okazji, jeśli dodam warunek V, jest to uniwersalne narzędzie do rozwiązywania problemów, można by wyeliminować warunek zależny od A, uruchamiając tylko algorytmy, które można udowodnić, że są uniwersalnymi rozwiązującymi problemy

Vanessa