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
0.8500838875770569
0 references
0.8168992400169373
0 references
0.8094263076782227
0 references
0.8065330386161804
0 references
0.7916280627250671
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