AF: Small: Logic and Computational Complexity

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

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.