4 ms·
NP hardness is defined in terms of worst-case hardness, not average case hardness. As long as there exists even one instance that makes your algorithm take non-
by Ar-Curunir 10y ago
NP hardness is defined in terms of worst-case hardness, not average case hardness. As long as there exists even one instance that makes your algorithm take non-polynomial amount of time to terminate, P won't be equal to NP.
- lotsoflumens 10y agoThat's why I'm becoming increasingly skeptical of the usefulness (in the scientific sense) of complexity theory as it's currently laid out. We already know that instances of NP-Hard problems are either easily solvable, in poly-time, or take exponential time, depending on the location of the instance in the problem space. For example in SAT, the distance of the instance to the critical clause/variable threshold. In subset sum, the density of the instance. It's not the problem class that matters.