Oracle-dependent properties of the lattice of NP sets
From MaRDI portal
Publication:795829
DOI10.1016/0304-3975(83)90003-8zbMATH Open0543.03024OpenAlexW2059997023MaRDI QIDQ795829FDOQ795829
Authors: Wolfgang Maass, S. Homer 
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90003-8
Recommendations
Cites Work
- Title not available (Why is that?)
- On the Structure of Polynomial Time Reducibility
- Recursively enumerable sets and degrees
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- On splitting recursive sets
Cited In (30)
- On simple and creative sets in NP
- On \(\Delta ^ P_ 2\)-immunity
- A classification of complexity core lattices
- Almost every set in exponential time is P-bi-immune
- Minimal pairs and complete problems
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- 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
- 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)
