The notion of NP-hardness covers the optimization variants of NP-complete problems. Very few people seem to understand what NP-completeness means anyway (including computer scientists), so I don’t think any of this matters anyway,
All the really important NP-complete problems are optimization ones. The decision-based definition is an accident of history and should be jettisoned.
-
-
-
Could you elaborate a bit more, please?
- Näytä vastaukset
Uusi keskustelu -
-
-
All NP-complete problems are similar and can be transformed in polynomial time and space from one to another. Why bother, if you see it as an optimization or decision problem?
-
I agree - an optimization problem whose decision variant is NP-complete can be solved by solving a polynomial number of NP-complete problems. If P=NP, then the optimization problems can still be solved in polynomial time. If P =/= NP then the complexity is still exponential.
Keskustelun loppu
Uusi keskustelu -
Lataaminen näyttää kestävän hetken.
Twitter saattaa olla ruuhkautunut tai ongelma on muuten hetkellinen. Yritä uudelleen tai käy Twitterin tilasivulla saadaksesi lisätietoja.