Z tego co rozumiem zarówno problemy NP-zupełne jak i NP-trudne są rozwiązywalne w czasie wykładniczym lub ponadwykładniczym (czyli dla małych n), a co je od siebie różni?
0
0
0
NP-trudny nie musi być NP.
CHYBA ;)
1
Problem NP trudny to taki do którego można sprowadzić wszystkie problemy klasy NP (za pomocą redukcji wielomianowej). Problem NP-zupełny jest problemem NP trudnym który jednocześnie należy do klasy NP.
Jeśli masz np. problem dla którego najwęższa klasa to PSPACE to jest NP-trudny, ale nie jest NP-zupełny bo leży poza klasą NP.
1
Shalom dobrze to wytłumaczył:) Ale popatrz na diagram w angielskiej wikipedii, który bardzo ładnie ilustruje jak się mają problemy NP trudne, zupełne do problemów NP oraz P.
0
Tutaj jest bardzo dobre wytłumaczenie zależności międzu problemami NP, NP-zupełnymi i NP-trudnymi. Polecam!
http://cpp0x.pl/kursy/Teoria-w-Informatyce/Zlozonosc-obliczeniowa/Klasy-problemow-NP/430
0
Szkoda że z błędami i to dość rażącymi...
- Podawanie wykresików gdzie P jest rozłączne z NP-zupełnymi i zawarte w NP (i wyraźnie z wykresu wynika że są problemy NP które nie są P) jest bardzo interesujące. Ciekawe czy autor odebrał już nagrodę za dowód że P!=NP
- Twierdzenie że w problemach klasy NP
znalezienie rozwiązania nie jest możliwe w czasie wielomianowym
to jest jakaś herezja. Po pierwsze z powodu który podałem w punkcie 1, po drugie dlatego że nawet gdyby P!=NP to nadal literka "P" w nazwie NP oznacza "polynomial" a autor ani slowem sie w tym tekście nie zająknął o maszynie turinga, tak deterministycznej jak i niedeterministycznej...
0
P!=NP
Takie problemy NP nie mają rozwiązania w czasie wielomianowym.
0
@Ciekawski o rly? To chyba mnie coś ominęło bo ostatnio jak sprawdzałem to problem P versus NP był nierozstrzygnięty.
Poza tym WSZYSTKIE problemy klasy NP mają rozwiązania wielomianowe. Ba, przecież to właśnie w ogóle oznacza klasyfikacja do NP. Że mają rozwiązania wielomianowe na niedeterministyczną maszynę turinga!
Szkoda słów.
0
@Ciekawski - odebrałeś już nagrodę Turinga?