摘要
本文研究了递归集的K-1-度上半格的格嵌入性,证明了任一可数分配格及任一可数偏序集均可嵌入〈R_K^1(NP_K^1);≤〉的任一区间.
The lattice embedability of the upper semilattice of K-1-degrees of recursive sets is studied. It has been proved that every countable distributive lattice and every countable partially ordered set can be embedded into any interval of <RK1(NPK1);≤>.
出处
《华中理工大学学报》
CSCD
北大核心
1990年第2期145-152,共8页
Journal of Huazhong University of Science and Technology
基金
国家自然科学基金
关键词
递归集
格嵌入性
K-1-度
上半格
Recursive set
Polynomial time reducibility
Polynomial time reducibility degree
Lattice embedability
