Computational Complexity Theory and Circuit Complexity

这一建议是为了支持对计算复杂性理论问题的持续研究。它提出了以下具体主题的详细攻击计划：算法随机性：非随机化领域的最新进展提供了将随机算法转换为确定性算法的工具。这产生了“算法信息论”（或“Kolmogorov复杂性”）和电路复杂性之间的新联系，这是一个意想不到的副产品。这可能会产生新的和有用的复杂性类的特征；已经得到了这类的一些初始定理。恒深电路：复杂度类ACC0（由And， Or和Modm门的有界深度电路计算的问题组成）引起了理论家的极大兴趣，因为(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.