计算机科学 ›› 2012, Vol. 39 ›› Issue (11): 179-182.
• 人工智能 • 上一篇 下一篇
樊硕,姜新文
出版日期:
发布日期:
Online:
Published:
摘要： 针对文献巨1]中提出的MSP问题(定义见正文)，从SA I'问题出发，给出sA}r问题到MSP问题的多项式归 结，进而给出MSP问题NP完全性质的另一种证明。
关键词: MSP问题，SAT问题，多项式归结，NP完全性
Abstract: According to the MSP problem (defined in the body) raised in paper[1]，this paper started from the SAT problem to the MSP problem. Thus we provided another proof to the NP-completeness of the MSP problem.
Key words: MSP problem, SAT problem, Polynomially reduction, NP-completeness
樊硕,姜新文. SAT问题可多项式归结到MSP问题[J]. 计算机科学, 2012, 39(11): 179-182. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2012/V39/I11/179
Cited
首页