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.

逻辑尝试描述具有某种限制格式描述的句子的性质。 计算复杂性研究了解决给定数学问题所需的计算机所需的步骤数。尽管主题的性质似乎是不相交的，但过去的逻辑和计算复杂性仍然具有丰富的相互作用历史。 Fagin的经典定理给出了NP的逻辑定义，这可能是该区域中的第一个连接之一。 在有限逻辑和计算复杂性的联系中，其他著名的结果包括互补的不确定性logspace的Immerman-Szelepsenyi定理； Ajtai在有限结构上的某些公式上的工作，这表明奇偶校验不是一阶定义的（事实证明这与Furst，saxe和Sipser的结果相当，表明平等的结果没有恒定的深度，多项式大小的电路）。 这些结果具有先进的逻辑和计算复杂性。该研究项目的灵感来自该项目的学生研究人员最近的工作，Swastik Kopparty和本·罗斯曼（Swastik Kopparty）和本·罗斯曼（Ben Rossman）在这些领域之间发掘了新的联系，从而取得了新的新结果。 该项目在逻辑和计算复杂性的交集中概述了新的问题，并概述了可以在这些问题上取得进展的方法。 一些具体问题包括： - 均匀对数深度电路的大小下限。-明确的功能对于一阶逻辑而言，很难通过任意模块化计数量化符（尤其是模量复合材料）进行一阶逻辑增强。-可选的无算法用于解决线性系统的无用算法。用于conjunctions conjunctions conjunctions conjunctions semantics querantics semantics semantics semantics semantics semantics。