ECCC-Report TR05-028https://eccc.weizmann.ac.il/report/2005/028Comments and Revisions published for TR05-028en-usThu, 03 Mar 2005 17:50:02 +0200
Paper TR05-028
| On the Lattice of Clones Below the Polynomial Time Functions |
Elmar BĂ¶hler
https://eccc.weizmann.ac.il/report/2005/028A clone is a set of functions that is closed under generalized substitution.
The set FP of functions being computable deterministically in polynomial
time is such a clone. It is well-known that the set of subclones of every
clone forms a lattice. We study the lattice below FP, which contains
other important function complexity classes like FL and FNC.
We show that the lattice is dualatomic and determine some of its dualatoms.
We show that no time-complexity class can be a dualatom in this lattice.
We show that there are uncountably many subclones of FP.
Thu, 03 Mar 2005 17:50:02 +0200https://eccc.weizmann.ac.il/report/2005/028