maxwell-cs
Lt. Junior Grade
- Registriert
- Juli 2007
- Beiträge
- 465
Wieso soll es nicht besser gehen?
NP-schwer impliziert nur (P != NP abnehmend), dass es keinen Polytime-Algo gibt. Ein Algorithmus mit Worstcase-Laufzeit (1+eps)^n mit kleinem eps kann immernoch existieren. Und selbst das gilt ja nur für die Worstcase-Laufzeit, vielleicht gibt es ja sogar einen Algorithmus, der auf vielen Instanzen in der Praxis sehr schnell ist (siehe TSP, L1-Steinertree, Coloring, MIP, ...).
NP-schwer impliziert nur (P != NP abnehmend), dass es keinen Polytime-Algo gibt. Ein Algorithmus mit Worstcase-Laufzeit (1+eps)^n mit kleinem eps kann immernoch existieren. Und selbst das gilt ja nur für die Worstcase-Laufzeit, vielleicht gibt es ja sogar einen Algorithmus, der auf vielen Instanzen in der Praxis sehr schnell ist (siehe TSP, L1-Steinertree, Coloring, MIP, ...).
