Complete sets and closeness to complexity classes (Q4727430)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4001484
Language Label Description Also known as
default for all languages
No label defined
    English
    Complete sets and closeness to complexity classes
    scientific article; zbMATH DE number 4001484

      Statements

      Complete sets and closeness to complexity classes (English)
      0 references
      1986
      0 references
      polynomial time
      0 references
      binary strings
      0 references
      polynomially close
      0 references
      Boolean closure
      0 references
      sparse sets
      0 references
      0 references
      Let A be a set of binary strings and let \(A_{\leq n}\) denote the set of strings of the length \(\leq n\) belonging to A. Two arbitrary sets A and B are said to be polynomially close if there exists a polynomial h such that for every \(n\geq 0| B_{\leq n}\Delta A_{\leq n}| \leq h(n)\). The author shows that the class of sets that are polynomially close to P, is the Boolean closure of the sparse sets and the sets in P. No EXPTIME- hard set can be polynomially close to any set in P. For each class of sets \({\mathcal C}\) and a set A if A is polynomially close to \({\mathcal C}\) and polynomially paddable (i.e. there exists a polynomial-time computable function pad such that \(x\in A\Leftrightarrow pad(x,y)\in A)\) then A is polynomial-time positively reducible to some member of \({\mathcal C}\).
      0 references

      Identifiers