Algorytmy i struktury danych · Senior · Pytanie 57 z 75
Co oznacza, że problem jest NP-zupełny?
- 1Udowodniono, że żaden algorytm go nie rozwiąże
- ✓Poprawna odpowiedź: Jest w NP, a każdy problem z NP sprowadza się do niego
- 3Rozwiąże go wyłącznie komputer niedeterministyczny
Wyjaśnienie
Rozwiązania można szybko sprawdzić, ale nie jest znany wielomianowy algorytm ich znajdowania. Wielomianowy algorytm dla dowolnego problemu NP-zupełnego rozwiązałby całe NP. Przykłady: SAT, kolorowanie grafu, subset sum.