NP-完全性与限制性分拆

一、引言 可以利用不确定的图林机(Turing Machine)在多项式时间内解决的问题称为NP-问题。在这类问题中,有些问题具有这样的性质:所有NP-问题都可以经过多项式的时间转化为这些问题。我们称这些问题为NP-完全的。例如,众所周知的“货郎担”问题就是一个NP-完全问题。人们认为NP-问题是否可解是当代数学和计算机科学中尚未解决的重大问题。