Ocena brak

Jakie byłyby konsekwencje udowodnienia, że wybrany problem NP – zupełny nie może być rozwiązany deterministycznym algorytmem o złożoności czasowej wielomianowej?

Autor /Barnim7777 Dodano /29.12.2011

Gdyby udowodniono, że choćby jeden z problemów NP – zupełnych z pewnością nie ma rozwiązania deterministycznie wielomianowego, znaczyłoby to, że inne problemy tej klasy także go nie mają. Wynika to z zależności, że jeden problem tej klasy można w czasie wielomianowym przekształcić w inny.

Do góry