« NTIME, pojęcie, C++ »
NTIME - Złożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga. (pojęcie)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
Opracował: Piotr DejaVu Szawdyński

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(nX) = NP
  • NTIME(Xn) = NEXPTIME
W powyższych wzorach 'n' określa liczbę danych wejściowych, natomiast 'X' jest stałą.

Zagadnienia powiązane

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

Linki zewnętrzne