%0 Journal Article
%T msp问题np完全性研究
%A 吴添君 姜新文？
%J 计算机科学
%D 2015
%R 10.11896/j.issn.1002-137X.2015.07.003
%X 针对文献[1,2]提出的msp问题,研究了msp问题与着色问题、子图同构问题的对应关系,揭示了msp问题所反映的np完全问题的共性；分析了msp问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
%K msp问题
%K np完全
%K 问题归结
%K 相变
%U http://www.jsjkx.com/jsjkx/ch/reader/view_abstract.aspx?file_no=20150703&flag=1