5 ms·

What about the problem of a solution to P and NP being ambiguous for practical uses? I read this argument somewhere, but can't find it now: Case 1, it's proved

What about the problem of a solution to P and NP being ambiguous for practical uses? I read this argument somewhere, but can't find it now: Case 1, it's proved that P = NP, and the complexity of solving an NP problem is N^1000. Case 2, it's proved that P != NP, and the complexity of solving an NP problem is N^log log log log N. In both cases, the result is technically correct (case 1 is polynomial, case 2 is exponential), but from a practical standpoint this proof that P != NP is much more world changing than this proof that P = NP. For example, you'd have to have a problem size that's measured in hundreds of digits before even getting to N^3!

eru 11y ago
In practice we find that algorithms in P usually have small exponents. And thus P is a good shorthand for tractable. If case 2 happens, we'll have to change our shorthand to what we actually care about: tractability. Similar arguments apply to case 1. (We know quite a bit about how a proof of NP ?= P could _not_ look like, because people already proved that certain strategies for a proof don't work. I am not sure if we can already rule out N^log log log log N, but it wouldn't surprise me.)
- dllthomas 11y ago
  "In practice we find that algorithms in P usually have small exponents." We find that algorithms we have identified in P usually have small exponents. This may simply be selection bias, if we are poor at coming up with n^4+ algorithms.
- infogulch 11y ago
  So, "P" and "NP" are just one possible set of precise definitions for "tractable" and "intractable", and so far they have aligned nicely so they can be used interchangeably (and it's unlikely to change much).
  - eru 11y ago
    Actually, NP isn't too intractable in practice. We are routinely solving huge instances of NP hard problems these days. There are problems that we hope are hard in the average case. Like breaking cryptography.

eru 11y ago

In practice we find that algorithms in P usually have small exponents. And thus P is a good shorthand for tractable. If case 2 happens, we'll have to change our shorthand to what we actually care about: tractability. Similar arguments apply to case 1. (We know quite a bit about how a proof of NP ?= P could _not_ look like, because people already proved that certain strategies for a proof don't work. I am not sure if we can already rule out N^log log log log N, but it wouldn't surprise me.)

dllthomas 11y ago
"In practice we find that algorithms in P usually have small exponents." We find that algorithms we have identified in P usually have small exponents. This may simply be selection bias, if we are poor at coming up with n^4+ algorithms.
infogulch 11y ago
So, "P" and "NP" are just one possible set of precise definitions for "tractable" and "intractable", and so far they have aligned nicely so they can be used interchangeably (and it's unlikely to change much).
- eru 11y ago
  Actually, NP isn't too intractable in practice. We are routinely solving huge instances of NP hard problems these days. There are problems that we hope are hard in the average case. Like breaking cryptography.