NPC问题中几个基本定理的证明

摘要：

就NPC问题(NP-complete,NP完全问题)中的几个基本定理给出了证明.首先从基本的团问题、SAT问题和图的着色问题入手,证明了它们都属于NPC问题,再利用独立集、顶点覆盖、有向图、团、SAT和图的着色等问题本身的内在关系,对其他的定理做了一一证明.

关键词：NPC问题、SAT、着色、独立集、顶点覆盖、有向图、无向图、哈密顿道路、回路

所属期刊栏目：8

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2012-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：19-21