SAT问题可多项式归结到MSP问题
SAT문제가다항식귀결도MSP문제
Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem
  • 万方数据
    计算机科学 계산궤과학
    COMPUTER SCIENCE
    2012年 11期 179-182 ,共4页

    樊硕%姜新文

    번석%강신문

    MSP问题%SAT问题%多项式归结%NP完全性 MSP問題%SAT問題%多項式歸結%NP完全性
    MSP문제%SAT문제%다항식귀결%NP완전성
    针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明.
    침대문헌[1]중제출적MSP문제(정의견정문),종SAT문제출발,급출SAT문제도MSP문제적다항식귀결,진이급출MSP문제NP완전성질적령일충증명.
    원문보기 원문다운로드 사이트로이동
저자의 최근 논문