Nietrudne problemy do rozwiązania w stałym czasie?

Stały czas jest absolutnie niskim stopniem złożoności czasu. Można się zastanawiać: czy jest coś nietypowego, co można obliczyć w stałym czasie? Jeśli trzymamy się modelu maszyny Turinga, niewiele można zrobić, ponieważ odpowiedź może zależeć tylko od początkowego odcinka wejścia o stałej długości, ponieważ dalsze części wejścia nie mogą być osiągnięte nawet w stałym czasie.

Z drugiej strony, jeśli przyjmiemy nieco bardziej wydajny (i bardziej realistyczny) model pamięci RAM kosztu jednostkowego, w którym elementarne operacje na liczbach są liczone jako pojedyncze kroki, wówczas możemy być w stanie rozwiązać nietrywialne zadania, nawet w stałym czasie. Oto przykład: $O(\log n)$

Instancja: liczby całkowite , każda podana w formacie binarnym przez bity . $n, k, l, d$ $O(\log n)$

Pytanie: Czy istnieje wykres werteksowy, taki że jego łączność z wierzchołkami wynosi , jego łączność z krawędzią wynosi , a jego minimalny stopień to ? $n$ $k$ $l$ $d$

Zauważ, że z definicji nie jest nawet oczywiste, że problem dotyczy NP . Powodem jest to, że naturalny świadek (wykres) może potrzebować długiego opisu , podczas gdy dane wejściowe są podawane tylko przez bity . Z drugiej strony na ratunek przychodzi następujące twierdzenie (patrz: ekstremalna teoria grafów B. Bollobasa). $\Omega(n^2)$ $O(\log n)$

Twierdzenie: Niech będą liczbami całkowitymi. Istnieje wykres werteksów z łącznością wierzchołków , łącznością krawędzi i minimalnym stopniem , 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.$

Ponieważ warunki te można sprawdzić w stałym czasie (w modelu RAM o koszcie jednostkowym), twierdzenie prowadzi do algorytmu stałego czasu w tym modelu.

Pytanie: Jakie są inne nietrywialne przykłady algorytmów stałego czasu?

cc.complexity-theory ds.algorithms time-complexity Andras Farago
źródło

Czy liczy się weryfikacja probabilistycznie sprawdzalnego dowodu?

David Eppstein,

Nie myśl, że twoim przykładem jest czas

. Dane wejściowe mają długość

, w którym to przypadku typowe słowo RAM zezwala na operacje

w jednym kroku. (Alternatywą jest umożliwienie wyrażenia proporcjonalnego do długości wejściowej, ale w takim przypadku można nazwać wiele algorytmów „stałego czasu”). Można spróbować dodać ciąg długości

po tych liczbach, ale wtedy I nie widzę, jak sprawdzanie tego formatu działałoby w

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ czas: wydaje się, że musisz sprawdzić (powiedzmy przez wyszukiwanie binarne), że całkowita długość łańcucha rzeczywiście wynosi

, co wymaga

czasu.

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Ryan Williams

Myślę, że sugestia Davida Eppsteina wskazuje bardziej interesujący kierunek: rozważenie losowych algorytmów czasu O (1). Przynajmniej w takim przypadku można mieć nadzieję, że dostęp do każdego bitu wejściowego będzie możliwy w co najmniej jednym możliwym przebiegu algorytmu.

Ryan Williams

Prostym przykładem randomizowanych algorytmów czasu O (1) jest przybliżona mediana (przybliżona w tym sensie, że podzieli dane wejściowe w przybliżeniu 50-50). Po prostu wybierz losowo 1000000 elementów z wejścia równomiernie, oblicz ich medianę i wyślij ją.

Jukka Suomela,

Podoba mi się twoje pytanie, ale wadą twojego przykładu jest to, że opiera się on na matematycznym twierdzeniu. Przesuwając to do granicy można powiedzieć: Instancja Dodatnie liczby całkowite

. Pytanie Czy istnieje liczba całkowita

taka, że

(odpowiedź to Prawda lub Fałsz). Cóż, rzeczywiście istnieje algorytm stałego czasu, ponieważ odpowiedź zawsze brzmi „Fałsz”, ale najwyraźniej nie jest to rodzaj przykładów, których sobie życzysz.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

J.-E.

Odpowiedzi:

W artykule Algorytmy aproksymacji stałej wartości czasu przez lokalne ulepszenia autorstwa Nguyen i Onak podają wiele przykładów schematów aproksymacji losowego stałego czasu: Maksymalne dopasowanie (czas działania zależy tylko od maksymalnego stopnia wykresu), Ustawienie okładki itp. Autorzy przedstawić metodę projektowania takich algorytmów.

Lamine
źródło

Istnieje wiele przykładów gier badanych w kombinatorycznej teorii gier, w których stan gry można opisać za pomocą stałej liczby wartości całkowitych. W przypadku niektórych z nich zwycięską strategię gry można obliczyć w stałym czasie. Ale rodzą też pytania o to, jaki dokładnie jest twój model obliczeniowy.

Jedną z najprostszych i najbardziej podstawowych gier kombinatorycznych jest nim: jedna ma stałą liczbę stosów ziaren, a jednym ruchem możesz usunąć dowolną liczbę ziaren z jednego stosu, wygrywając lub przegrywając (w zależności od wybranych zasad) jeśli weźmiesz ostatnią fasolę. Optymalną strategię można obliczyć w stałym czasie, jeśli zezwolisz na bitowe operacje logiczne xor (tj. Operator ^ w językach programowania takich jak C / C ++ / Java / itp.) Czy jest to algorytm stałego czasu w twoim modelu?

Oto jeden, w którym wiadomo, że istnieje algorytm deterministyczny dokładny w czasie stałym (w możliwie nierealistycznym rozszerzonym modelu obliczeń, który pozwala testować pierwotność liczby w stałym czasie), ale nie wiadomo, czym jest ten algorytm: biorąc pod uwagę początek ruch w grze monet Sylver , określ, czy jest to ruch wygrywający czy przegrywający. Schemat blokowy tego problemu podano w Berlecamp, Conway i Guy, Winning Ways , ale zależy to od skończonego zestawu kontrprzykładów do ogólnej charakterystyki zwycięskich ruchów i nie wiadomo, co to jest za zestaw (a nawet czy to jest pusty).

Kolejnym interesującym przykładem z teorii gier kombinatorycznych jest gra Wythoffa. Każda pozycja gry może być opisana przez parę liczb całkowitych (tj. Stała przestrzeń, w twoim modelu obliczeniowym), ruchy w grze polegają na zmniejszeniu jednej z tych dwóch liczb całkowitych do mniejszej wartości, a strategia wygranej obejmuje przejście do pozycji, w której stosunek między tymi dwiema liczbami całkowitymi jest jak najbardziej zbliżony do złotego podziału. Ale w wielu pozycjach gry jest wybór: możesz zmniejszyć większą z dwóch liczb całkowitych do punktu, w którym jest to (prawie) mniejsza liczba całkowita razy złoty stosunek lub mniejsza liczba całkowita podzielona przez złoty stosunek. Tylko jedna z tych dwóch opcji będzie zwycięskim ruchem. Tak więc optymalną strategię można zdefiniować w kategoriach stałej liczby operacji arytmetycznych, ale operacje te obejmują liczbę nieracjonalną, złoty współczynnik. Czy to algorytm stałego czasu w twoim modelu? Może to' $n$ $\log n$

David Eppstein
źródło

Dziękuję, to są wszystkie interesujące przykłady. Ładnie rzucają też światło na fakt, że pojęcie „stałego czasu” jest mniej jasne, niż pierwotnie myślałem ...

Andras Farago

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ $|G|$ $m$ $m$ $m$

orgesleka
źródło