NTIME

[pojęcie] Złożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga.

Opis szczegółowy

NTIME określa złożoność czasową algorytmu, rozpatrywanego na niedeterministycznej maszynie Turinga. Zapis ten wykorzystuje się głównie do opisywania klas złożoności.

Zapis NTIME(f(n)) oznacza, że rozpatrywanym modelem obliczeń jest niedeterministyczna maszyna Turinga, której złożoność czasowa algorytmu wynosi f(n), gdzie 'n' określa liczbę danych wejściowych. Niedeterministyczna maszyna Turinga oznacza, że w wyniku działania algorytmu uzyskujemy uzyskujemy np. zbiór danych (który równie dobrze może być pusty).

Dodatkowe informacje

NTIME(n^X) = NP
NTIME(Xⁿ) = NEXPTIME

W powyższych wzorach 'n' określa liczbę danych wejściowych, natomiast 'X' jest stałą.

Zagadnienia powiązane

DTIME	Złożoność czasowa algorytmu, rozpatrywana na deterministycznej maszynie Turinga. (pojęcie)
klasy złożoności	Zbiory problemów obliczeniowych o podobnych złożonościach obliczeniowych. (pojęcie)
problem NP	Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)

Linki zewnętrzne

http://en.wikipedia.org/wiki/NTIME

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.