NP完全问题及其应用

摘要

图灵于20世纪30年代提出了一个理想化的计算模型-图灵机模型,该模型用一个无限长的带子作为存储,有一个能在带子上读写和前后移动的读写头.该模型形式简单,对现代计算理论的发展具有非常重要的意义,它奠定了计算理论的基础.利用该模型,定义了如下两类问题:1.N类问题；2.NP类问题。本文从以下四个方面分析了NP完全问题及其应用：1.NP完全性的形式定义及其重要定理。2.NP完全问题的最新应用。3.NP完全问题的相变现象。4.NP完全问题解决策略。