3 ms·
Any NP-Complete problem will have cases that are trivial. The complexity of the problems is how they grow in the worst case.
by paulgb 14y ago
Any NP-Complete problem will have cases that are trivial. The complexity of the problems is how they grow in the worst case.
- rfurmani 14y agoCorrection: every natural NP-complete problem will have easy cases. You can construct problems for which there is no easy case, which is a shame since I thought at one point you could use this trait to seperate P and NP
- paulgb 14y agoInteresting. How do you need to define "easy" for this to work? Can you give an example of a problem without an easy solution? Has this class of problem been studied?