Czy można zdecydować, czy dany algorytm jest asymptotycznie optymalny?

Czy istnieje algorytm dla następującego problemu:

Biorąc pod uwagę maszynę Turinga która decyduje o języku , czy istnieje maszyna Turinga decydująca tak że ? $M_1$ $L$
$M_2$ $L$ $t_2(n) = o(t_1(n))$

Funkcje i są najgorszym przypadku prowadzenia razy maszyn Turinga i , odpowiednio. $t_1$ $t_2$ $M_1$ $M_2$

Co ze złożonością przestrzeni?

complexity-theory computability undecidability decision-problem StaticBug
źródło

Odpowiedź zdecydowanie nie jest. Określenie najgorszego czasu działania TM jest znane z nierozstrzygalności.

chazisop

Bardziej ogólne pytanie .

Raphael

Odpowiedzi:

Oto prosty argument pokazujący, że są nierozstrzygalne, tzn. Nie ma algorytmów sprawdzających, czy dany algorytm jest optymalny pod względem czasu działania lub zużycia pamięci.

Zmniejszamy problem zatrzymania na czystej taśmie do twojego problemu dotyczącego optymalności czasu działania.

Niech będzie daną maszyną Turinga. Niech N będzie następującą maszyną Turinga: $M$

: na wejściu 1. Uruchom na czystej taśmie dla (co najwyżej) kroków. 2. Jeśli nie zatrzymuje się krokami, uruchom pętlę o rozmiarze , a następnie zwróć NO. 3. W przeciwnym razie zwróć TAK. $N$ $n$
$M$ $n$
$M$ $n$ $2^n$

Istnieją dwa przypadki:

Jeśli nie zatrzyma się na czystej taśmie, maszyna będzie działać przez kroków na wejściu . Zatem jego czas działania wynosi . W tym przypadku jest oczywiście optymalne. $M$ $N$ $\Theta(2^n)$ $n$ $\Theta(2^n)$ $N$
Jeśli zatrzymuje się na pustej taśmie, wówczas maszyna będzie działać przez stałą liczbę kroków dla wszystkich wystarczająco dużych , więc czas działania wynosi . W tym przypadku jest oczywiście optymalne. $M$ $N$ $n$ $O(1)$ $N$

W skrócie:

M halts on blank tape \Leftrightarrow N is optimial

$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$

$M$ $N$ $N$ $M$

Podobny argument można zastosować do przestrzeni, tzn. Nierozstrzygalne jest sprawdzenie, czy dana maszyna Turinga jest optymalna pod względem zajmowanej przestrzeni.

Nawet silniejsze stwierdzenie jest prawdziwe: nie możemy zdecydować, czy dana funkcja obliczeniowa jest górną granicą złożoności czasowej obliczania danej funkcji obliczeniowej. Podobnie w przypadku przestrzeni kosmicznej. Tj. Nawet podstawowa teoria złożoności nie może być zautomatyzowana przez algorytmy (co można uznać za dobrą wiadomość dla teoretyków złożoności;).

Kaveh
źródło

M_{1}

$M_1$

n

$n$

n \mapsto YES

$n \mapsto \textrm{YES}$

N

$N$

n_{0}

$n_0$

n

$n$

n_{0}

$n_0$

M

$M$

Ach, pytanie się zmieniło, odkąd go ostatnio przeczytałem. Nieważne.

Raphael

@ PålGD, myślę, że OP wykorzystało to jako przykład (na podstawie pierwotnego pytania opublikowanego w cstheory). Możesz sprawdzić komentarze pod tym pytaniem.

Kaveh

Jak wspomnieli inni, odpowiedź brzmi „nie”.

Ale jest interesujący artykuł napisany przez Bluma „ Niezależna od maszyny teoria złożoności funkcji rekurencyjnych ”. Pokazał, że istnieją pewne funkcje z tą właściwością, bez względu na to, jak szybki może być program do obliczania tych funkcji, istnieje inny program do ich obliczania znacznie szybciej .

bardzo ładna nieruchomość!

Reza
źródło

-3

Ha! Gdyby odpowiedź brzmiała tak, żylibyśmy w innym świecie.

$A_0$ $A$ $L$ $A_0$ $A$

Niestety nie jest to możliwe i rzeczywiście osobiście uważam, że udowodnienie (nietrywialne) optymalności jest najciekawszym (i trudnym) problemem w informatyce. O ile mi wiadomo - chętnie bym poprawił - nie ma żadnego wyniku optymalizacyjnego dla jakiegokolwiek problemu wielomianowego (z wyjątkiem trywialnych wyników optymalizacyjnych przebiegu algorytmów zajmujących czas proporcjonalny do wielkości wejściowej).

t do t
źródło

Ω (N)

$\Omega(N)$

Ω (n \log n)

$\Omega(n \log n)$

@vonbrand - to miałem na myśli przez algorytmy proporcjonalne do wielkości wejściowej.

t do

@ttothet Ok, obawiam się, że to będzie bezowocne, ale spróbuję ponownie. 1) Nie, wcale nie. Jeśli zapisujesz tylko jeden krok na każdym wejściu, masz lepszy algorytm niż wcześniej, nawet jeśli ma ten sam asymptotyczny czas działania. 2) Nie, nie ma. Może to również oznaczać „nie wiem, ale jeśli tak, to X”. Nie jest to rzadkie (por. P? = NP). 3) Użytkownik twierdził istniały żadne nietrywialne dolne granice (na asymptotyka, zakładam) w ogóle . To jest złe. Proszę odrobić pracę domową.

Raphael

@ MartinJonáš Mam na myśli 2-taśmową maszynę Turinga. Kaveh ma rację, dowód na to, że twierdzenie o hierarchii czasowej daje rozwiązania problemów z czasem polime o arbitralnie wysokiej złożoności, ale przykłady nie są do końca naturalne i nie wydają się bardzo wyraźne. Ponadto nie znana jest hierarchia czasu probabilistycznego, więc naprawdę nie mamy nic.

Sasho Nikolov