even if quantum computer is made, it only speeds up

even if quantum computer is made, it only speeds up

所有跟贴·加跟贴·新语丝读书论坛

送交者: steven 于 2010-03-29, 16:49:15:

回答: 老赛，机器学习要能光靠记忆就好了，或者对我们来说糟了：）由自如于 2010-03-29, 16:13:00:

some problems solving. If NP != P, even Quantum computer won't be able to solve NP complete problems, let alone EXP-Time problems like chess or go.

That's exactly the point: how do you think human brain solves GO then? - 自如 (274 bytes) 2010-03-29, 17:32:08 (427055)
- Go is not NP-hard, it is EXPTIME, a much bigger class. - steven (364 bytes) 2010-03-29, 17:57:45 (427071)
  - NP-hard includes EXPTIME (Note that I didn't say NP-complete) - 自如 (936 bytes) 2010-03-29, 18:16:00 (427083)
    - No that is not true, EXPTIME is bigger, - steven (227 bytes) 2010-03-29, 18:52:42 (427089)
      - What did I say that is not true? Note that I said NP-hard, not NP. - 自如 (373 bytes) 2010-03-29, 19:10:05 (427093)
        
        generally when we say NP, means problems can be solved - steven (276 bytes) 2010-03-29, 19:51:09 (427101)
        
        Sure, no disagreement here - 自如 (222 bytes) 2010-03-29, 20:27:24 (427120)
        
        Yes, that has to do with polynomial time turing reduction. - steven (585 bytes) 2010-03-29, 20:54:00 (427135)
        
        I actually asked about a different thing, but it doesn't matter :) - 自如 (126 bytes) 2010-03-29, 23:07:55 (427193)
        
        you meant the name NP-Hard? It is the official name. (无内容) - steven (0 bytes) 2010-03-30, 00:22:13 (427199)
        
        The problem in NP-Hard has to be solvable in poly-time with an oracle machine. - steven (159 bytes) 2010-03-29, 19:34:35 (427096)
        
        Another problem due to definition :) - 自如 (97 bytes) 2010-03-29, 19:48:16 (427100)