OnP-subset structures
From MaRDI portal
Recommendations
Cites work
- A classification of complexity core lattices
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Bi-immune sets for complexity classes
- Completeness, Approximation and Density
- scientific article; zbMATH DE number 4010508 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Immunity, Relativizations, and Nondeterminism
- On Isomorphisms and Density of NP and Other Complete Sets
- On Reducibility to Complex or Sparse Sets
- On splitting recursive sets
- Optimal Approximations and Polynomially Levelable Sets
- Oracle-dependent properties of the lattice of NP sets
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- The complexity of theorem-proving procedures
- The density and complexity of polynomial cores for intractable sets
- Unit Refutations and Horn Sets
Cited in
(8)- A classification of complexity core lattices
- The structure of generalized complexity cores
- The algebraic structure of the isomorphic types of tally, polynomial time computable sets
- On inefficient special cases of NP-complete problems
- Set-theoretic structure of computable sets
- Characterizations and existence of easy sets without hard subsets
- scientific article; zbMATH DE number 3885884 (Why is no real title available?)
- scientific article; zbMATH DE number 4197420 (Why is no real title available?)
This page was built for publication: OnP-subset structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3789542)
