Ocena brak

Jakie byłyby konsekwencje skonstruowania dla wybranego problemu NP – zupełnie deterministycznego algorytmu o złożoności wielomianowej?

Autor /Barnim7777 Dodano /29.12.2011

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.

Do góry