Oracle-dependent properties of the lattice of NP sets. (English) Zbl 0543.03024

The paper considers questions about the lattice of NP sets, together with the sublattice P, under the assumption \(P\neq NP\). Two properties of NP sets are considered; whether there are any simple sets in NP and whether every infinite NP set contains an infinite subset in P. An NP-simple set is a coinfinite set in NP whose complement contains no infinite NP set. Oracles are constructed relative to which \(P\neq NP\) and for which the statement that NP-simple sets exist is true, respectively false. Similarly, it is shown that any argument which solves the problem of whether every infinite NP set contains an infinite P subset does not relativize. In particular an oracle B is constructed relative to which \(P^ B\neq NP^ B\) and every infinite set in \(NP^ B\) contains an infinite \(P^ B\) subset. The considerations are analogous to the study of the lattices of recursively enumerable and recursive sets. The constructions are somewhat more sophisticated than those previously used in this context.


03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Baker, T.; Gill, J.; Solovay, R., Relativizations of the P ≟ NP question, SIAM J. Comput., 4, 4, 431-442 (1975) · Zbl 0323.68033
[2] Baker, T.; Selman, A., A second step toward the polynomial hierarchy, Proc. 17th IEEE Symp. on the Foundations of Computer Science, 71-75 (1976)
[3] Bennett, C. H.; Gill, J., Relative to a random oracle \(A, P^A\) ≠ \(NP^A\) ≠ co-\(NP^A\) with probability one, SIAM J. Comput., 10, 1, 96-113 (1981) · Zbl 0454.68030
[4] Breidbart, S., On splitting recursive sets, J. CSS, 17, 56-64 (1978) · Zbl 0392.03028
[5] Hopcroft, J.; Ullman, A., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[6] Ladner, R., On the structure of polynomial time reducibility, J. Assoc. Comput. Mach., 22, 155-171 (1975) · Zbl 0322.68028
[7] Soare, R. I., Recursively enumerable sets and degrees, Bull. Amer. Math. Soc., 84, 1149-1181 (1978) · Zbl 0401.03018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.