SAT问题可多项式归结到MSP问题

SAT问题可多项式归结到MSP问题

樊硕;姜新文

【期刊名称】《计算机科学》 【年(卷),期】2012(039)011

【摘要】According to the MSP problem (defined in the body) raised in paper[1], this paper started from the SAT problem and gave the polynomial reduction algorithm from the SAT problem to the MSP problem. Thus we provided another proof to the NP-completeness of the MSP problem.%针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明.

【总页数】4页(179-182)

【关键词】MSP问题;SAT问题;多项式归结;NP完全性 【作者】樊硕;姜新文

【作者单位】国防科技大学计算机学院 长沙410073;国防科技大学计算机学院 长沙410073 【正文语种】中文 【中图分类】TP301.5 【相关文献】

1.P(多项式算法)问题对NP(非多项式算法)问题——7个\千年大奖问题\之一 [J],

2.初等对称多项式的多项式表出的三类对称多项式 [J], 于萍; 陈文争

3.一类包含契贝谢夫多项式-盖根堡多项式--勒让德多项式的积的和 [J], 李超; 刘端森

4.确定有限域上给定周期的不可约多项式的个数以及利用低次不可约多项式构造高次不可约多项式 [J], 虞培全

5.对代数教学多项式的可约性、多项式的根及最大公因子问题的研究 [J], 沈景清

以上内容为文献基本信息，获取文献全文请下载