4 ms·
> That is not entirely true what are you referring to? Obviously x^4 != x^10, but noone has ever proven that "if SAT is P, then it would have the lowest (or h
by firechickenbird 4y ago
> That is not entirely true
what are you referring to?
Obviously x^4 != x^10, but noone has ever proven that "if SAT is P, then it would have the lowest (or highest) polynomial complexity among the other problems", or anything similar
- Hendrikto 4y agoI was referring to this: > [All NP-hard problems] have equivalent difficulty. I get what OP meant, but there can still be some NP-hard problems that are more difficult than others. As I said, x^4 and x^10 are both polynomials. I wouldn‘t call them "equivalent" though.