Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem
SAT问题可多项式归结到MSP问题

Keywords: MSP problem,SAT problem,Polynomially reduction,NP-completeness
MSP问题，SAT问题，多项式归结，NP完全性

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对文献巨1]中提出的MSP问题(定义见正文)，从SA I'问题出发，给出sA}r问题到MSP问题的多项式归 结，进而给出MSP问题NP完全性质的另一种证明。

Full-Text