第140章 (第8/9页)
古藤提示您：看后求收藏（猫扑小说www.mpzw.tw），接着再看更方便。
“你这里提出图灵机的概念，你能具体讲一下什么是图灵机吗？”
“图灵机有些抽象，想象你只有纸带和一个类似于打字机一样的，能够沿着纸带写0或1的自动写字装置......
如果这样一个图灵机存在，那我们就获得了可怕的力量：有一个机器可以执行任意可以用图灵机标识的的算法了......”
吴老听完姜凡讲完，对图灵机有了一个大概的了解，随后他有翻了几页问道！
“关于NP-complete，为什么要单独把NP里最难的问题拿出来？”
“最开始的时候，大家不知道NP的定义是存在所谓，最难的这么一个东西的，各类问题没有固定的比较标准......”
“证明了任何一个NP形式的问题都可以转换成3SAT（某个NP问题），3SAT就是说有n个variable，m个clause......”
“......”
姜凡和吴老足足又探讨了一个多小时！
