Computational Complexity Theory and Circuit Complexity

计算复杂性理论和电路复杂性

• 批准号: 0514155
• 负责人: Eric Allender
• 金额: $ 20万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-15 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514155&HistoricalAwards=false
• 关键词: Computational; Complexity; Theory; Circuit

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.

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