Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Opracował: Piotr DejaVu Szawdyński
Pojęcia

Teoria złożoności obliczeniowej

[kategoria] Zagadnienia związane z teorią złożoności obliczeniowej.

Wykaz elementów dowiązanych

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)
NTIME Złożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga. (pojęcie)
problem decyzyjny Opisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem NP Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)
problem NP-Trudny Znalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową. (pojęcie)
problem NP-Zupełny Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej oraz nie jest możliwe rozwiązanie problemu ze złożonością obliczeniową wielomianową. (pojęcie)
problem optymalizacyjny Opisanie problemu w taki sposób, że jego rozwiązaniem jest najlepszy możliwy do uzyskania wynik. (pojęcie)
problem P Znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)
problem przeszukiwania Opisanie problemu w taki sposób, że jego rozwiązaniem jest zbiór wyników spełniających warunki wynikające z opisu problemu. (pojęcie)
złożoność obliczeniowa Ilość operacji jakie trzeba wykonać aby został zrealizowany dany algorytm, posiadając określoną ilość danych wejściowych. (pojęcie)