Oracle-dependent properties of the lattice of NP sets (Q795829)

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.