NP-zupełne problemy
 
Encyklopedia PWN
NP-zupełne problemy,
mat. problemy obliczeniowe o szczególnych własnościach z punktu widzenia teorii złożoności obliczeniowej;
p.NP-z. należy do klasy NP, a zatem może być teoretycznie szybko rozwiązywany przez idealny model niedeterministycznej maszyny Turinga (hipoteza P≠NP), a ponadto zawiera informację wystarczającą do rozwiązania dowolnego innego problemu z klasy NP (co w ścisłym sensie oznacza istnienie efektywnej redukcji dowolnego problemu z klasy NP do p.NP-z.); znalezienie szybkiego algorytmu dla dowolnego p.NP-z. (dokładniej: algorytmu działającego w czasie zależnym wielomianowo od rozmiaru danych wejściowych) wystarczyłoby do obalenia hipotezy P≠NP; przypuszcza się jednak, że problemy te nigdy nie będą efektywnie i z pełną dokładnością rozwiązywane przez komputer; p.NP-z. obejmują wiele ważnych zagadnień praktycznych; historycznie pierwsze było zagadnienie spełnialności formuł rachunku zdań; p.NP-z. jest też np. pytanie, czy daną mapę można pokolorować 3 kolorami.
zgłoś uwagę
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia