3 ms·
That'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 th
by lotsoflumens 10y ago
That'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.