Oracle-dependent properties of the lattice of NP sets
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.
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- On splitting recursive sets
- On the Structure of Polynomial Time Reducibility
- Recursively enumerable sets and degrees
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On some natural complete operators
- Reductions among polynomial isomorphism types
- On \(\Delta ^ P_ 2\)-immunity
- A classification of complexity core lattices
- On simple and creative sets in NP
- Diagonalizations over polynomial time computable sets
- Simplicity, immunity, relativizations and nondeterminism
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- Polynomial-time compression
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Minimal pairs and complete problems
- Recursion-theoretic ranking and compression
- On the lattices of NP-subspaces of a polynomial time vector space over a finite field
- Resource bounded immunity and simplicity
- A note on separating the relativized polynomial time hierarchy by immune sets
- scientific article; zbMATH DE number 3902038 (Why is no real title available?)
- Bi-immune sets for complexity classes
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- Immunity and simplicity in relativizations of probabilistic complexity classes
- A second step toward the strong polynomial-time hierarchy
- Towards the Actual Relationship Between NP and Exponential Time
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- scientific article; zbMATH DE number 1555920 (Why is no real title available?)
- Almost every set in exponential time is P-bi-immune
- The structure of relativized P and NP questions
- Immunity and pseudorandomness of context-free languages
- A result relating disjunctive self-reducibility to P-immunity
- Complexity-theoretic algebra. II: Boolean algebras
- Bi-immunity results for cheatable sets
This page was built for publication: Oracle-dependent properties of the lattice of NP sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795829)
