Czy pamiętasz, czym jest problem NP-pełny? Czym różni się od zwykłego NP?

NP (niedeterministyczny czas wielomianowy) — to klasa problemów, dla których rozwiązanie można sprawdzić w czasie wielomianowym. To znaczy, jeśli masz kandydat na odpowiedź, możesz szybko sprawdzić, czy jest poprawny.

Problemy NP-pełne to podzbiór NP, które są jednocześnie najbardziej "trudne" w tej klasie. Gdyby ktoś znalazł algorytm wielomianowy rozwiązujący dowolny problem NP-pełny, to wszystkie problemy z NP można by rozwiązać w czasie wielomianowym.

Główna różnica:

• NP — problemy, których rozwiązania można szybko sprawdzić.
• NP-pełne — problemy z NP, do których można sprowadzić dowolny inny problem NP (czyli są "najbardziej skomplikowane" w NP).

Przykład: problem maksymalnego kliku w grafie jest NP-pełny, a problem sprawdzania, czy podzbiór elementów sumuje się do zadanego numeru, jest w NP.