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.