@Dru: Najprościej mówiąc problem klasy NP to taki problem do którego rozwiązania potrzeba bardzo dużo czasu. Do rozwiązania niektórych problemów klasy NP potrzeba więcej czasu niż szacowana długość istnienia wszechświata, przy założeniu, że używalibyśmy superwydajnych komputerów. Przykładowo mamy dużą ilość miast i mamy odwiedzić każde miasto tak aby suma przejechanych km była jak najmniejsza. Sprawdzenie każdej możliwości naszej trasy zajęłoby gigantyczną ilość czasu. Pytanie jest takie czy problem klasy NP można
@Dru: W skrócie: jest sobie klasa problemów zwanych NP. Przykładowe to znalezienie drogi przez n miast tak aby każde odwiedzić jedynie raz czy znalezienie rozwiązania formuły logicznej tak aby była ona prawdziwa. To czy rozwiązaliśmy problem poprawnie sprawdzić jest bardzo prosto. Liczba operacji jaką należy wykonać w tym celu jest ograniczona przez pewien wielomian a[c]n^c + a[c-1]n^(c-1) + ... a[1]*n + a[0], asymptotycznie to się oznacza O(n^c) czyli istnieje taka funkcja
Komentarze (7)
najlepsze
http://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa#Czy_P_.3D_NP.3F
http://pl.wikipedia.org/wiki/Problem_NP