A low and a high hierarchy within NP
作者：
Highlights：
•
摘要
A low and a high hierarchy within NP are defined. The definition is similar to the jump hierarchies below the degree of the halting problem. For this purpose a complexity theoretic counterpart of the jump operator in recursion theory is defined. Some elementary properties of these hierarchies are investigated. The high hierarchy is, in some sense, a hierarchy of generalized NP-completeness notions.
论文关键词：
论文评审过程：Received 4 October 1981, Revised 13 September 1982, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(83)90027-2
