OnP-subset structures (Q3789542)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	OnP-subset structures	scientific article

Statements

scholarly article

0 references

OnP-subset structures (English)

0 references

zbMATH Open document ID

0 references

10.1007/BF01692061

0 references

0 references

0 references

Mathematical Systems Theory

0 references

publication date

1987

0 references

Mathematics Subject Classification ID

0 references

zbMATH DE Number

0 references

zbMATH Keywords

lattice structure

0 references

complexity class P

0 references

P-immune

0 references

almost P-immune

0 references

intractable sets

0 references

MaRDI profile type

MaRDI publication profile

0 references

A linear-time algorithm for testing the truth of certain quantified Boolean formulas

0 references

Bi-immune sets for complexity classes

0 references

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

0 references

On Isomorphisms and Density of $NP$ and Other Complete Sets

0 references

On splitting recursive sets

0 references

The complexity of theorem-proving procedures

0 references

0 references

Unit Refutations and Horn Sets

0 references

Oracle-dependent properties of the lattice of NP sets

0 references

0 references

Completeness, Approximation and Density

0 references

On Reducibility to Complex or Sparse Sets

0 references

A classification of complexity core lattices

0 references

Optimal Approximations and Polynomially Levelable Sets

0 references

The density and complexity of polynomial cores for intractable sets

0 references

0 references

Immunity, Relativizations, and Nondeterminism

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3789542

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3789542&oldid=34787534"