4 ms·

> P=NP in that a solution can be used to attack RSA encryption. Note that 1) P=NP does not necessarily give raise to any polynomial algorithm that solves a NP

> P=NP in that a solution can be used to attack RSA encryption. Note that 1) P=NP does not necessarily give raise to any polynomial algorithm that solves a NP problem. The proof would prove the existence of one such algorithm, but it might well never be found (which is the current status quo) 2) even if it would be polynomial, it could still run longer than the heat of the universe. O(n) = n^10000000 would still be a polynomial runtime for example. The second reason is why Donald Knuth does think that P=NP might be possible.

drdeca 7y ago
Isn’t there some (highly impractical) algorithm which dovetails through different Turing machines, in a way that has an asymptotically optimal runtime for a given problem, just with really terrible constants? I thought we knew an algorithm that, if P=NP, would solve NP problems in P time, (but with absurd constants), and otherwise solves the problems is worse than polytime. But I could be remembering this totally wrong.
- schwurb 7y ago
  > (highly impractical) Forget everything practical - we are in deep theoretic waters here! There are thousands of algorithm with even a polynomial solution where you still go for the heuristic because the polynomial version is way to slow. > Isn’t there some (highly impractical) algorithm which dovetails through different Turing machines, in a way that has an asymptotically optimal runtime for a given problem, just with really terrible constants? Optimal might be, as long as optimal does not mean polynomial. Otherwise you would read about it in the newspapers ;) I don't know of such algorithm, but "trying out different turing machines" gives me a strong gut feeling of "not polynomial". > I thought we knew an algorithm that, if P=NP, would solve NP problems in P time, (but with absurd constants), and otherwise solves the problems is worse than polytime. Is that the algorithm you are refering to? Sounds like what Turing proposed once. The interesting branch is the P=NP, since then you could answer really really interesting things in P. Theoretically - and if indeed P=NP ;)
  - drdeca 7y ago
    this doesn't say the exact algorithm (I haven't found it), but this stack overflow answer talks about it : https://stackoverflow.com/questions/5107140/what-is-meant-by-dovetailing https://stackoverflow.com/questions/5107140/what-is-meant-by...

drdeca 7y ago

Isn’t there some (highly impractical) algorithm which dovetails through different Turing machines, in a way that has an asymptotically optimal runtime for a given problem, just with really terrible constants? I thought we knew an algorithm that, if P=NP, would solve NP problems in P time, (but with absurd constants), and otherwise solves the problems is worse than polytime. But I could be remembering this totally wrong.

schwurb 7y ago
> (highly impractical) Forget everything practical - we are in deep theoretic waters here! There are thousands of algorithm with even a polynomial solution where you still go for the heuristic because the polynomial version is way to slow. > Isn’t there some (highly impractical) algorithm which dovetails through different Turing machines, in a way that has an asymptotically optimal runtime for a given problem, just with really terrible constants? Optimal might be, as long as optimal does not mean polynomial. Otherwise you would read about it in the newspapers ;) I don't know of such algorithm, but "trying out different turing machines" gives me a strong gut feeling of "not polynomial". > I thought we knew an algorithm that, if P=NP, would solve NP problems in P time, (but with absurd constants), and otherwise solves the problems is worse than polytime. Is that the algorithm you are refering to? Sounds like what Turing proposed once. The interesting branch is the P=NP, since then you could answer really really interesting things in P. Theoretically - and if indeed P=NP ;)
- drdeca 7y ago
  this doesn't say the exact algorithm (I haven't found it), but this stack overflow answer talks about it : https://stackoverflow.com/questions/5107140/what-is-meant-by-dovetailing https://stackoverflow.com/questions/5107140/what-is-meant-by...