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.

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