OnP-subset structures

DOI10.1007/BF01692061zbMath0646.03035MaRDI QIDQ3789542

David A. Russo, Pekka Orponen

Publication date: 1987

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01692061

zbMATH Keywords

lattice structure; intractable sets; almost P-immune; complexity class P; P-immune

Mathematics Subject Classification ID

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

Related Items

The structure of generalized complexity cores, On inefficient special cases of NP-complete problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• A classification of complexity core lattices
• On splitting recursive sets
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Immunity, Relativizations, and Nondeterminism
• Bi-immune sets for complexity classes
• The density and complexity of polynomial cores for intractable sets
• Optimal Approximations and Polynomially Levelable Sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• Unit Refutations and Horn Sets
• On Reducibility to Complex or Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of theorem-proving procedures