AF: Small: Logic and Computational Complexity

AF：小：逻辑和计算复杂性

• 批准号: 0915155
• 负责人: Madhu Sudan
• 金额: $ 15.32万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915155&HistoricalAwards=false
• 关键词: AF; Small; Logic; Computational; Complexity

Logic attempts to describe the nature of sentences that have descriptions in some restricted format. Computational complexity investigates the number of steps needed on a computer to solve a given mathematical problem. Despite the seemingly disjoint nature of the topics, Logic and Computational Complexity have had a rich history of interactions in the past. Fagin's classical theorem giving a logical definition of NP is probably one of the first connections in the area. Other celebrated results in the nexus of finite logic and computational complexity include the Immerman-Szelepsenyi theorem showing non-deterministic logspace is closed under complementation; and Ajtai's work on certain formulae on finite structures, which shows that parity is not first-order definable (which turns out to be equivalent to Furst, Saxe, and Sipser's result that parity does not have constant depth, polynomial size circuits). These results have advanced logic as well as computational complexity.This research project is inspired by recent work by the student investigators on this project, Swastik Kopparty and Ben Rossman who have unearthed new connections between these areas leading to several new results. This project outlines novel further questions in the intersection of logic and computational complexity and outlines methods that may be employed to make progress on these questions. Some specific questions include:- Size lower bounds for uniform logarithmic depth circuits.- Explicit functions that are hard for first-order logic augmented with arbitrary modular counting quantifiers (modulo composites in particular).- Choiceless algorithms for solving linear systems.- Decidability of the containment problem for conjunctive queries under multiset semantics.

逻辑试图描述具有某种受限制格式的描述的句子的性质。 计算复杂性研究计算机解决给定数学问题所需的步骤数。尽管这些主题看似互不相交，但逻辑和计算复杂性在过去有着丰富的相互作用历史。 费金的经典定理给出了 NP 的逻辑定义，这可能是该领域最早的联系之一。 有限逻辑和计算复杂性关系中的其他著名结果包括 Immerman-Szelepsenyi 定理，该定理显示非确定性对数空间在互补条件下是封闭的； Ajtai 对有限结构上的某些公式的研究表明奇偶校验不是一阶可定义的（结果相当于 Furst、Saxe 和 Sipser 的结果，即奇偶校验不具有恒定深度、多项式大小的电路）。 这些结果具有先进的逻辑和计算复杂性。该研究项目的灵感来自该项目的学生研究人员 Swastik Kopparty 和 Ben Rossman 最近的工作，他们发现了这些领域之间的新联系，从而得出了一些新结果。 该项目概述了逻辑和计算复杂性交叉领域的新的进一步问题，并概述了可用于在这些问题上取得进展的方法。 一些具体问题包括：- 统一对数深度电路的大小下界。- 对于一阶逻辑来说很难的显式函数，用任意模块化计数量词（特别是模复合）进行增强。- 用于求解线性系统的无选择算法。- 的可判定性多集语义下联合查询的包含问题。