Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-028 | 12th February 2005 00:00

On the Lattice of Clones Below the Polynomial Time Functions

RSS-Feed




TR05-028
Authors: Elmar Böhler
Publication: 3rd March 2005 17:50
Downloads: 2920
Keywords: 


Abstract:

A 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.



ISSN 1433-8092 | Imprint