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

problem P

[pojęcie] Znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej.

Opis szczegółowy

Problem P - problem decyzyjny w którym znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej.

Problem P należy do zbioru problemów NP. Z tego wynika, że:
  • Sprawdzenie poprawności rozwiązania danego problemu jest możliwe w czasie wielomianowym;
  • Znalezienie rozwiązania danego problemu jest możliwe w czasie wielomianowym.

Zagadnienia powiązane

problem decyzyjnyOpisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem NPSprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)

Linki zewnętrzne