NP完全性理论中关于集合恰当覆盖的一个证明

NP完全性理论是国际上数学与计算机科学理论研究的新领域.本文证明了NP完全性理论中关于集合恰当覆盖的一个结论,充实了NPC理论中关于集合覆盖的论证.

不仅要正确而且还要有效——NP完全性理论简介

求解问题的方法正确与否当然是相当重要的,但仅有正确性还不够因为一个正确的无效方法仍是无用的,故方法的有效性也是很重要的。这一点直到本世纪七十年代才被人们真正认识。1971年美国人S.A.Cook在《定理证明过程的复杂性》中证明了第一个NP完全问题,从而为NP完全性理论奠定了基础。从那时起,这一理论一直是数学和计算机科学工作者研究的重要领域之一。算法就是求解问题的一种方法的实现。