摘要
我们在[11]中证明了多项式时间强图灵归约≤_(sn)T 与多项式时间多一归≤_(pm)有表现在完全集上的本质差别,在本文中我们证明了递归集的≤_(sn)T-归约约度上半格〈(?)_k^1;≤〉不可分配,籍此得〈(?)_k^1;≤〉与〈(?)_m^p;≤〉不同构.这表明此二种归约有表现在其度结构上的差别.此外,使用对角线技术我们还证明了〈(?)_k^1;≤〉的某些初始片段不可补.
出处
《数学学报（中文版）》
SCIE
CSCD
北大核心
1989年第4期517-524,共8页
Acta Mathematica Sinica：Chinese Series
