For over thirty years, computational complexity theory has provided the computer science community with a theoretical backbone from which one can understand the power of computation. Computational complexity has produced the tools that allows one to understand what likely can and cannot be computed in a reasonable amount of time and memory. This research will continue this tradition. While this research will look at a wide range of problems in many different areas of computational complexity it will focus on two interesting directions. The project first looks at a new model of computation, quantum computing. Computer scientists have recently discovered the powerful applications of the cancellation effect of quantum physics. Though these quantum computers do not yet exist, nice theoretical models of these machines allow study of their complexity. The research will look at ways to apply the cancellation effects in the well-studied area of counting complexity to help the understanding of the complexity of quantum computation. The research will also embark on a more ambitious plan of attempting complexity class separation, one of the most important and least successful directions in the area. In particular, the research will try to show languages in computable in nondeterministic polynomial time, such as the famous traveling salesman problem, cannot be computable in (logarithmic) amount of space. The research well use tools recently developed by the PI of simulating space and time by alternation and applying Post's program of looking at properties of these and other classes. By understanding the relationship among complexity classes, one can better understand the nature of computation and provide the necessary directions one needs to solve problems on various models of computation. This research will help strengthen the theoretical foundations from which computer science stands.
