Zu diesem lizenzpflichtigen Artikel gibt es eine Open Access Version, die kostenlos und ohne Lizenzbeschränkung gelesen werden kann. Die Open Access Version kann inhaltlich von der lizenzpflichtigen Version abweichen.
Preisinformation
Bitte wählen Sie ihr Lieferland und ihre Kundengruppe
The authors consider under the assumption P not equal to NP questions concerning the structure of the lattice of NP sets together with the sublattice P. They show that two questions which are slightly more complex than the known splitting properties of this lattice cannot be settled by arguments which relativize. The two questions which they consider are whether every infinite NP set contains an infinite P subset and whether there exists an NP-simple set. They construct several oracles, all of which make P not equal to NP, and which in addition make the above-mentioned statements either true or false. In particular they give a positive answer to the question, raised by Bennett and Gill (1981), whether an oracle B exists making PB not equal to NPB and such that every infinite set in NPB has an infinite subset in PB. The constructions of the oracles are finite injury priority arguments.