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

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

排序问题的递归关系

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

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

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