4 ms·

I think even a negative solution could have practical implications. For starters you can now know for sure the problem can't be solved efficiently, which means

I think even a negative solution could have practical implications. For starters you can now know for sure the problem can't be solved efficiently, which means you can stop looking and focus on other things. Possibly you can use it in situations you need a hard problem lkke in crypto (although there is more to it then that, since just because a problem is NP doesnt mean that a specific instance is) I am not a complexity theorist, but ive always doubted the n^1000 solution to p=np being likely. Think about it - that essentially means you have to loop through the data 1000 times, but no more than that, no matter how much data. It just doesn't seem natural that looping 999 wouldn't be enough, but 1000 would be precisely enough. Its a sort of middle ground that seems like it would be extremely odd to me. Much more so than p=np with a low exponent or p!=np.

smueller1234 3y ago
Apologies for nitpicking, but n^m doesn't mean m loops (ie n^1000 dient mean 1000 passes): that would be mn (1000n in your example). I think your intuition argument kind of breaks down there.
- laszlokorte 3y ago
  Not 1000 iterations of 1 loop, but 1000 loops nested inside each other.
- bawolff 3y ago
  I meant to say 1000 nested loops. You're right to call me out on it though, as that is a huge difference in meaning. I still think it would be bizarre to have to nest a loop n layers deep, where n-1 is not enough, but n layers is sufficient for really large n. Like what extra info would you get on the 1000th nested loop that you didn't on the first 999. Of course there is nothing formal about this, it just feels like it would be wrong to me (and hence personally i would consider it the most interesting result). Of course gut feelings dont really count for much and i have nothing more than that. I suppose my intuition is that increasing the exponent gives diminishing returns to how much more power you really get , so it doesn't make sense for problems to be in the n^1000 range. My gut feeling is they should either be easier or harder. I certainly can't think of very many non-exponential algorithms in the > n^50 range.

smueller1234 3y ago

Apologies for nitpicking, but n^m doesn't mean m loops (ie n^1000 dient mean 1000 passes): that would be mn (1000n in your example). I think your intuition argument kind of breaks down there.

laszlokorte 3y ago
Not 1000 iterations of 1 loop, but 1000 loops nested inside each other.
bawolff 3y ago
I meant to say 1000 nested loops. You're right to call me out on it though, as that is a huge difference in meaning. I still think it would be bizarre to have to nest a loop n layers deep, where n-1 is not enough, but n layers is sufficient for really large n. Like what extra info would you get on the 1000th nested loop that you didn't on the first 999. Of course there is nothing formal about this, it just feels like it would be wrong to me (and hence personally i would consider it the most interesting result). Of course gut feelings dont really count for much and i have nothing more than that. I suppose my intuition is that increasing the exponent gives diminishing returns to how much more power you really get , so it doesn't make sense for problems to be in the n^1000 range. My gut feeling is they should either be easier or harder. I certainly can't think of very many non-exponential algorithms in the > n^50 range.