Topics in Complexity Theory

三十多年来，计算复杂性理论为计算机科学界提供了一个理论支柱，从中人们可以理解计算的力量。计算复杂性产生了一些工具，使人们能够理解在合理的时间和内存中可能可以计算什么，不可以计算什么。这项研究将延续这一传统。虽然这项研究将关注计算复杂性的许多不同领域的广泛问题，但它将关注两个有趣的方向。该项目首先着眼于一种新的计算模型——量子计算。计算机科学家最近发现了量子物理抵消效应的强大应用。虽然这些量子计算机还不存在，但这些机器的良好理论模型允许研究它们的复杂性。该研究将着眼于如何将抵消效应应用于已经得到充分研究的计算复杂性领域，以帮助理解量子计算的复杂性。该研究还将开始一个更雄心勃勃的计划，即尝试复杂类分离，这是该领域最重要也是最不成功的方向之一。特别是，研究将试图证明在不确定的多项式时间内可计算的语言，如著名的旅行推销员问题，不能在（对数）空间中计算。本研究充分利用了PI新近开发的空间和时间交替模拟工具，并应用Post程序观察这些类和其他类的性质。通过理解复杂性类之间的关系，人们可以更好地理解计算的本质，并为解决各种计算模型上的问题提供必要的方向。这项研究将有助于加强计算机科学的理论基础。

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.