Computational Complexity Theory and Circuit Complexity

这一建议是为了支持对计算复杂性理论中问题的继续研究。它针对以下具体主题提出了详细的攻击计划：算法随机性：去随机化领域的最新进展提供了将随机化算法转换为确定性算法的工具。这在算法信息论(或Kolmogorov复杂性)和电路复杂性之间产生了新的联系，这是一种意想不到的副产品。这可能产生新的和有用的复杂性类的特征；已经获得了这类初始定理。恒定深度电路：复杂类ACC0(由与、或和模门的有限深度电路计算的问题组成)引起了理论家的极大兴趣，因为(A)它是已知的最小的电路类，它不能计算NP中的所有问题，(B)相反，它似乎与已知的不能计算一些非常简单的函数的电路类密切相关。由于最近的结果给出了ACC0的新的图论特征，并且由于新的结果将算术复杂性与布尔复杂性联系起来，因此建议重新关注试图证明ACC0的下界的问题，以及将最近的刻画扩展到更复杂的类的问题。约束满足问题：人工智能和数据库理论(以及其他领域)中的许多重要问题都可以表示为约束满足问题。关于这些问题的一个基本定理是，在多项式时间等价之前，只有两类问题。它们要么在P中，要么是NP-完全的。最近与合作者的工作表明，如果考虑用于研究P的子类的自然可约性，则不再存在二分法，而是将其划分为六类等价的问题。拟议活动的智力优点：本活动的目标是澄清复杂性类之间的关系，这是目前可用于理解现实世界计算问题的计算复杂性的最佳工具。其中一些问题是出了名的难解，但最近的进展证明了一些乐观的理由，即可以获得关于这些复杂类别的更多有用的见解。拟议活动产生的广泛影响：该提议的一个重要部分是对研究生的支持请求。除了帮助获得研究成果外，这种支持还将起到培训新的研究人员和教育工作者的作用。这种支持还将帮助学生参加专业会议和研讨会，并有助于加强这些机构，这些机构是传播这些研究成果的主要论坛。计算复杂性研究的长期目标如果最终实现，将对社会产生深远的影响(例如，通过为公钥密码学提供坚实的数学基础，公钥密码学目前依赖于许多未经证实的猜想)。这项拟议的研究为朝着这一长期目标逐步取得进展提供了具体计划。

This proposal is for support of continuing research on problems in computational complexity theory. It presents detailed plans of attack on the following specific topics:Algorithmic Randomness: Recent progress in the field of derandomization gives tools to convert randomized algorithms into deterministic ones. This yields new connections between \Algorithmic Information Theory" (or \Kolmogorov Complexity") and circuit complexity as an unexpected side-product. This may yield novel and useful characterizations of complexity classes; some initial theorems of this sort have been obtained.Constant-Depth Circuits: The complexity class ACC0 (consisting of problems computed by bounded-depth circuits of And, Or, and Modm gates) is of great interest to theoreticians, because (a) it is the smallest class of circuits not known to be unable to compute every problem in NP, and (b) in contrast, it seems to be very closely related to classes of circuits known to be unable to compute some very simple functions. Becauseof recent results that give new graph-theoretic characterizations of ACC0, and because of new results that relate arithmetic complexity to Boolean complexity, it is proposed that renewed attention be placed on the problem of trying to prove lower bounds for ACC0, and on the problem of extending the recent characterizations to more complexity classes.Constraint Satisfaction Problems: Many important problems in artificial intelligence and in database theory (and elsewhere) can be expressed as constraint satisfaction problems. One of the fundamental theorems about these problems is that, up to polynomial-time equivalence, there are only two kinds of problems. Either they are in P, or they are NP-complete. Recent work with collaborators suggests that if one considersthe natural reducibilies that are used to investigate subclasses of P, then there is no longer a dichotomy, but instead a partition into six classes of equivalent problems.Intellectual merit of the proposed activity: The goal of this activity is to clarify the relationship among complexity classes, which is the best tool currently available for understanding the computational complexity of real-world computational problems. Some of these problems are notoriously dificult, but recent progress justifies some optimism that additional useful insight about these complexity classes can be obtained.Broader impacts resulting from the proposed activity: An important part of this proposal is a request for support for a graduate student. In addition to helping obtain research results, this support would have the effect of training a new researcher and educator. This support would also help the student to participate in professional meetings and workshops, and help strengthen those institutions, which are the principal forums for dissemination of these research results. The long-term goals of research in computational complexity, if finally achieved, will have profound impact on society (for instance, by providing firm mathematical underpinnings to public-key cryptography, which currently rests upon many unproven conjectures). The proposed research offers concrete plans for incremental progress toward this long-range goal.