首页 | 本学科首页   官方微博 | 高级检索  
     


The existence of minimal honest polynomial degree below and recursively enumerable degrees
Authors:Yang Dongping
Affiliation:(1) Institute of Software, Academia Sinica, China
Abstract:
In [1] Homer introduced the honest polynomial reducibility and proved that under this new reducibility a set of minimal degree below O″ is constructed under the assumption thatP=NP. In this paper we will prove that under the same assumption a set of minimal degree can be constructed below any recursively enumerable degrees. So under the honest polynomial reducibility a set of low minimal degree does exist.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号