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

针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明。

递归集的强多项式时间归结度对的性质

本文研究强多项式时间归结度上半格【TSN;≤T】和【mSN;≤m】的代数性质。证明了对任意给定度,存在度和使得,且,但不存在。籍此上半格【TSN;≤T】和【mSN;≤m】不是格;任意给定的度都是极小对的一半。进一步,我们证明了存在度使得且没有度有性质。

特殊形式和结构的MSP问题NP完全性研究

针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义。因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究。

_n^p和■_n^p的递归可表示性

通过对△np与△np(A)两类复杂性语言中的多项式图灵完全集之间关系的研究,证明了pn、■pn等计算复杂性语言类的递归可表示性。

排序问题的递归关系

介绍了排序问题和它们的多项式时问归结,给出并证明了两个重要的排序问题的归结关系.