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.

该建议是为了支持对计算复杂性理论问题的持续研究。它列出了以下特定主题的攻击计划的详细计划：算法随机性：derandomization领域的最新进展提供了将随机算法转换为确定性的工具。这产生了\算法信息理论“（或\ kolmogorov的复杂性”）与电路复杂性作为意外的副产品之间的新联系。这可能会产生复杂性类别的新颖和有用的特征。已经获得了这种最初的定理。稳定的深度电路：复杂性ACC0（由由有限的深度电路计算的问题组成，理论家和MODM大门都非常感兴趣）是理论家的极大兴趣，因为（a）众所周知，这是最小的circuits counce of Circe counce of Counce of Counce of Counce of的np和（b），这是（b）的反应（b）。无法计算一些非常简单的功能。因为最近的结果给出了ACC0的新图形理论特征，并且由于将算术复杂与布尔值复杂性相关的新结果，因此提议将重新注意的注意力放在试图证明ACC0的降低范围的问题上，以及证明对最近的特征性问题的问题，以及许多重要的问题：构成的理论是人工智能的问题：许多重要的问题：满意问题。关于这些问题的基本定理之一是，直到多项式时间等效性，只有两种问题。他们要么在P中，要么是NP完整的。与合作者的最新工作表明，如果一个人考虑用于调查P子类的自然还原，那么不再有二分法，而是将六类分配给六类等效问题。拟议活动的智能优点：该活动的目标是阐明当前的复杂工具，即在计算中的最佳工具，即在计算中阐明了该工具的最佳计算。众所周知，其中一些问题是很重要的，但是最近的进步证明了一些乐观的态度，即可以获得有关这些复杂性类别的其他有用的见解。造成的拟议活动产生的影响：该提案的重要部分是对研究生提供支持。除了帮助获得研究结果之外，这种支持还将培训新的研究人员和教育者。这种支持还将帮助学生参加专业会议和讲习班，并帮助加强这些机构，这些机构是传播这些研究结果的主要论坛。如果最终实现，计算复杂性研究的长期目标将对社会产生深远的影响（例如，通过向公共钥匙密码学提供公司数学基础，目前基于许多未经证实的猜想）。拟议的研究提供了朝着这个远程目标朝着增量进步的具体计划。