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 等数据库收录! |