图灵机和计算复杂性理论-高压无刷电机方案

2.3 图灵机和计算复杂性理论 上一节的NP完全理论虽然直观，但是不严密。我们没有给出Cook定理的证明， 因为在证明这个定理之前需要给“问题”下一个严格定义，否则是没有办法说明什么 是“NP问题”，更别提证明任何一个NP问题都可以多项式归约到它了。此外，对“算 法”也需要进行严格证明，否则没有办法定义归约。如果说上一节是从感性上认识问题 复杂性和NP完全理论，那么从这一节开始正式介绍相关理论。 2.3.1 问题和语言 在深入讨论之前，需要先对“问题”做一个严格定义。抽象问题(abstract prob- lem) 是一个I和S的二元关系，其中I是实例(instance) 集合，S是解(solution) 集 合。NP完全理论只考虑判定问题(decision problem) ，即S={0, 1}。对于优化问题，