Oracle-dependent properties of the lattice of NP sets

DOI10.1016/0304-3975(83)90003-8zbMath0543.03024OpenAlexW2059997023MaRDI QIDQ795829

Wolfgang Maass, Homer, Steven

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

zbMATH Keywords

theory of computationOraclessimple setsinfinite NP setintractable problemslattice of NP sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Related Items (27)

Reductions among polynomial isomorphism types ⋮ Minimal pairs and complete problems ⋮ On \(\Delta ^ P_ 2\)-immunity ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ A classification of complexity core lattices ⋮ On simple and creative sets in NP ⋮ Diagonalizations over polynomial time computable sets ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ On the lattices of NP-subspaces of a polynomial time vector space over a finite field ⋮ OnP-subset structures ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ Complexity-theoretic algebra. II: Boolean algebras ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ Recursion-theoretic ranking and compression ⋮ Bi-immunity results for cheatable sets ⋮ Immunity and pseudorandomness of context-free languages ⋮ A second step toward the strong polynomial-time hierarchy ⋮ 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 ⋮ Almost every set in exponential time is P-bi-immune ⋮ Resource bounded immunity and simplicity ⋮ On some natural complete operators ⋮ Towards the Actual Relationship Between NP and Exponential Time ⋮ Bi-immune sets for complexity classes

Cites Work

• Unnamed Item
• On splitting recursive sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Recursively enumerable sets and degrees

This page was built for publication: Oracle-dependent properties of the lattice of NP sets