Topics in Space Bounded Computation

点击翻译按钮获取中文摘要

The goal of this research is to study space bounded computations. Even though space bounded computations are somewhat less difficult to analyze than time bounded computations, little is known regarding the power of nondeterminism. This research attempts to understand underlying combinatorics in space bounded computations by looking at various restricted models of computation. The DSPACEılog n! =? NSPACEılog n! problem is approached by considering different models such as sublog space bounded machines, universal traversal sequence and multihead two way finite state automaton. These restricted models of computation raise interesting questions with direct consequence to DSPACEılog n! =? NSPACEılog n! problem. This research concentrates on developing and using tools like communication complexity to show lower bounds on space requirement in these models with the hope of understanding the space bounded computations.