4 ms·

Thanks, I hope I'll be able to convince him to register and answer to you guys. From what I gathered, the implication if he was right, would be the end of encr

by guilamu 11y ago

Thanks, I hope I'll be able to convince him to register and answer to you guys. From what I gathered, the implication if he was right, would be the end of encryption.

tgflynn 11y ago
The implications would be far greater than that if he were right. An efficient algorithm for an NP complete problem would mean that you could find global optima for general non-linear functions. That would very likely lead to superhuman AI.
- guilamu 11y ago
  Holy Christ!
  - tgflynn 11y ago
    Yeah, that's the thing about this problem, virtually infinite payoff if you succeed and virtually zero chance of success. The human mind isn't very good at dealing with that kind of cost-benefit ratio, it can drive people a little insane.
- schoen 11y ago
  I don't understand where your "very likely" comes from here; AI has quite a lot of challenges other than ones that we know how to describe as optimization problems. You can also in some cases have asymptotically efficient algorithms that aren't very efficient on the problem instances that we try to use them for; a somewhat recent example is the AKS primality test. https://en.wikipedia.org/wiki/AKS_primality_test#Importance https://en.wikipedia.org/wiki/AKS_primality_test#Importance
  - tgflynn 11y ago
    For your second objection by "efficient algorithm", I meant an algorithm that is practically efficient on very large problems. That probably means no worse than O(N^2), but preferably more like O( N*log(N) ). For your first objection I think a modified form of AIXI probably already solves most of the "non-optimization" challenges of AI. By modified form, I basically mean replace minimum size Turing Machines with minimum size boolean circuits to transform an uncomputable problem into one that is computable and that would be tractable given the scenario we are discussing. In other words you would essentially be doing reinforcement learning by searching for small boolean circuits which maximize the objective function. Of course there is the rather important matter of defining the objective function itself, which P=NP may not directly help much with. I think that with a sufficiently powerful optimization algorithm you will get (super-)intelligent behavior almost no matter what the objective function (as Boscom has argued with his paper-clip scenario). The question would be more whether the intelligent behavior that arises is desirable for humans or not. Even if you don't believe in my AIXI-like approach just look at what a highly suboptimal optimization algorithm like gradient ascent has done when applied to deep neural networks. If you can get superhuman go players and image recognizers with that, what would you get using a universal global optimizer ? Finally we are talking about a scenario where mathematics is basically a solved problem (in the sense that you would have an automatic theorem prover that could prove any theorem you could state formally). If that world wouldn't lead quickly to general AI then there would have to be some mystery to intelligence that is literally deeper than mathematics itself, which is hard for me to believe.
    - GFK_of_xmaspast 11y ago
      > That probably means no worse than O(N^2),... We don't even have a quadratic-time algorithm for matrix multiplication (and it's obvious that O(N^2) is a lower bound).
      - tgflynn 11y ago
        Nor do we have any proof of a lower bound > O( N ) for 3-SAT.

by guilamu 11y ago

Thanks, I hope I'll be able to convince him to register and answer to you guys. From what I gathered, the implication if he was right, would be the end of encryption.

tgflynn 11y ago

The implications would be far greater than that if he were right. An efficient algorithm for an NP complete problem would mean that you could find global optima for general non-linear functions. That would very likely lead to superhuman AI.

guilamu 11y ago
Holy Christ!
- tgflynn 11y ago
  Yeah, that's the thing about this problem, virtually infinite payoff if you succeed and virtually zero chance of success. The human mind isn't very good at dealing with that kind of cost-benefit ratio, it can drive people a little insane.
schoen 11y ago
I don't understand where your "very likely" comes from here; AI has quite a lot of challenges other than ones that we know how to describe as optimization problems. You can also in some cases have asymptotically efficient algorithms that aren't very efficient on the problem instances that we try to use them for; a somewhat recent example is the AKS primality test. https://en.wikipedia.org/wiki/AKS_primality_test#Importance https://en.wikipedia.org/wiki/AKS_primality_test#Importance
- tgflynn 11y ago
  For your second objection by "efficient algorithm", I meant an algorithm that is practically efficient on very large problems. That probably means no worse than O(N^2), but preferably more like O( N*log(N) ). For your first objection I think a modified form of AIXI probably already solves most of the "non-optimization" challenges of AI. By modified form, I basically mean replace minimum size Turing Machines with minimum size boolean circuits to transform an uncomputable problem into one that is computable and that would be tractable given the scenario we are discussing. In other words you would essentially be doing reinforcement learning by searching for small boolean circuits which maximize the objective function. Of course there is the rather important matter of defining the objective function itself, which P=NP may not directly help much with. I think that with a sufficiently powerful optimization algorithm you will get (super-)intelligent behavior almost no matter what the objective function (as Boscom has argued with his paper-clip scenario). The question would be more whether the intelligent behavior that arises is desirable for humans or not. Even if you don't believe in my AIXI-like approach just look at what a highly suboptimal optimization algorithm like gradient ascent has done when applied to deep neural networks. If you can get superhuman go players and image recognizers with that, what would you get using a universal global optimizer ? Finally we are talking about a scenario where mathematics is basically a solved problem (in the sense that you would have an automatic theorem prover that could prove any theorem you could state formally). If that world wouldn't lead quickly to general AI then there would have to be some mystery to intelligence that is literally deeper than mathematics itself, which is hard for me to believe.
  - GFK_of_xmaspast 11y ago
    > That probably means no worse than O(N^2),... We don't even have a quadratic-time algorithm for matrix multiplication (and it's obvious that O(N^2) is a lower bound).
    - tgflynn 11y ago
      Nor do we have any proof of a lower bound > O( N ) for 3-SAT.