Ocena brak
Jakie byłyby konsekwencje skonstruowania dla wybranego problemu NP – zupełnie deterministycznego algorytmu o złożoności wielomianowej?
Gdyby udowodniono, że choć jeden z algorytmów klasy NP – zupełnej posiada wielomianowe rozwiązanie udowodniono by równocześnie, że inne także go posiadają. Wynika to z faktu, że każdy problem tej klasy da się w czasie wielomianowym przekształcić w dowolny inny.