非经典计算模型及其计算复杂性研究

摘要

计算理论是讨论计算机的计算能力和计算效率问题的基础理论。计算能力，即可计算性问题，是对计算机能够计算的问题的一个判定；计算效率，即计算复杂性问题，是对计算机能否在规定时间、空间下计算一定规模问题的一个判定；计算能力与计算效率相辅相成，互为补充，构成了计算机科学与数学研究的一个重要方向。其理论模型为程序正确性验证与系统可靠性设计提供重要的理论依据；同时计算理论本身为人们认识理解智能与计算间的关系问题提供了一条途径。提高计算效率历来是计算机算法设计分析领域的重要课题，如何去衡量算法的执行效率需要一个统一的标准，计算理论提供了这个标准，并衍生出了一套关于这个标准的分析理论，为准确的描述计算效率提供了工具。
　　 非经典计算理论是相对于经典计算理论而言的，主要区别在于计算模型的变化，即对经典的图灵机模型做出随机化、模糊化的非确定性处理，得出可计算性和计算复杂性方面的相关结论，为人们认识量子计算和生物计算提供了一条途径，为人们解开智能之谜提供理论依据。
　　 这篇论文在论述了经典计算模型与相关计算复杂性结论之后，重点讨论了随机算法、模糊算法的理论模型和相关结论。对模糊计算的NP完全性，即λ截语言的接受问题，运用多项式时间归约作出了证明；对其不可近似性，即模糊语言的接受问题，运用引入间隙的归约作出了证明。非经典的计算模型主要性质是其非确定性，而非确定性的实现有赖于并行的列举出各个可能的解，当前兴起的“云计算”，即大规模分布式并行计算，可以为此提供物理基础，但计算模型是逻辑实体，需要用数学的方式表示出来，这就需要对“云计算”的计算模式进行抽象，准确的“云计算”的计算效率问题则需要计算复杂性的研究为其提供理论基础。可满足性问题是一个NP完全问题，其补问题是一个co-NP问题，直观上它难于可满足性问题，对此问题的“云计算”算法可以展示“云计算”的计算效率，论文给出了应用在云计算基础设施上的算法，该算法可以在多项式时间内给出可满足性问题及其补问题的解，从现实上证明了“云计算”的计算效率。