(non-deterministic polynomial time problem)
problem nalezacy do badanej od 1971 r. klasy problemów obliczeniowych, dla których nie sa znane algorytmy wielomianowe ani nie udowodniono istnienia wiekszej niz wielomianowa dolnej granicy zlozonosci obliczeniowej; niezwykle trudne zagadnienie teoretyczne algorytmiki.
- problem komiwojazera, minimalizacja kosztu...
- problem pokrycia wierzcholkowego, zagadnienie optymalizacyjne...
- problem pokrycia zbioru, (set covering proble...