Logical Approaches to Computational Barriers

Logspace Complexity of Functions and Structures

Speaker:
| Douglas Cenzer |

Author(s): |
Douglas Cenzer and Zia Uddin |

Slot: |
Array, 10:30-10:50, col. 5 |

We study the logspace complexity of various natural functions and structures, based on the notion of a Turing machine with input and output as in Papadmitriou (1995). For any $k>1$, we construct a logspace isomorphism between $\{0,1\}^*$ and $\{0,1,\dots,k\}^*$. We improve results of Cenzer and Remmel (1992) by characterizing the sets which are logspace isomorphic to $\{1\}^*$. We generalize Proposition 8.2 of Papadimitriou by giving upper bounds on the space complexity of compositions of functions. This is used to obtain the complexity of isomorphic copies of structures with different universes. Finally, we construct logspace models with standard universe $\{0,1\}^*$ of various additive groups, including $Z(p^\infty)$ and the rationals.

websites: Arnold Beckmann | 2006-06-28 |