Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Logspace Complexity of Functions and Structures


Speaker: Douglas Cenzer
Author(s): Douglas Cenzer and Zia Uddin
Slot: Array, 10:30-10:50, col. 5

Abstract

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