Oracle-dependent properties of the lattice of NP sets (Q795829): Difference between revisions

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.