Oracle-dependent properties of the lattice of NP sets
From MaRDI portal
(Redirected from Publication:795829)
Recommendations
Cites work
- 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
Cited in
(30)- On simple and creative sets in NP
- On \(\Delta ^ P_ 2\)-immunity
- A classification of complexity core lattices
- Minimal pairs and complete problems
- Almost every set in exponential time is P-bi-immune
- Simplicity, immunity, relativizations and nondeterminism
- Polynomial-time compression
- Resource bounded immunity and simplicity
- A note on separating the relativized polynomial time hierarchy by immune sets
- A second step toward the strong polynomial-time hierarchy
- The structure of relativized P and NP questions
- Immunity and simplicity in relativizations of probabilistic complexity classes
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- Bi-immune sets for complexity classes
- On some natural complete operators
- scientific article; zbMATH DE number 1555920 (Why is no real title available?)
- Towards the Actual Relationship Between NP and Exponential Time
- On the lattices of NP-subspaces of a polynomial time vector space over a finite field
- Reductions among polynomial isomorphism types
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Immunity and pseudorandomness of context-free languages
- scientific article; zbMATH DE number 3902038 (Why is no real title available?)
- A result relating disjunctive self-reducibility to P-immunity
- Complexity-theoretic algebra. II: Boolean algebras
- Bi-immunity results for cheatable sets
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- Diagonalizations over polynomial time computable sets
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Recursion-theoretic ranking and compression
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)
