NP-hart < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:33 Do 27.07.2006 | | Autor: | Bastiane |
Hallo schon wieder!
Wieso kann man sagen: "Leider ist dieses Problem NP-hart."?
Wieso "leider"? Was genau bedeutet das? NP-hart bedeutet doch, dass jedes Problem aus NP auf dieses Problem polynomiell reduzierbar ist. Und wieso kann das dann "leider" sein?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Hallo Bastiane!
Nach meinem Verständnis bezieht sich das "leider" eher darauf, dass das Problem insbesondere NP-schwer ist, also vermutlich kein schneller Algorithmus existiert.
Gruß, banachella
|
|
|
| |
|
Liebe Bastiane,
Banachella hat recht: wenn ein Problem A NP-hart ist, so sind also alle Probleme aus NP auf das Problem A polynomiell reduzierbar.
Wenn es nun einen polynomiellen Algorithmus für A gäbe, so wäre P=NP, und es vermuten halt viele, dass dem nicht so ist. Jedenfalls
ist in der Tat für ein NP-schweres Problem die Hoffnung auf einen effizienten Algorithmus nicht sehr gross.
Gruss,
Mathias
|
|
|
|
