Logic, Symmetry, and Complexity

逻辑、对称性和复杂性

• 批准号: 405342984
• 负责人: Professor Dr. Erich Grädel
• 金额: --
• 依托单位: Informatik 7: Lehr- und Forschungsgebiet für Mathematische Grundlagen der Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/405342984?language=en
• 关键词: Logic; Symmetry; Complexity

The central objective of this project is the investigation of the expressive and computational power of algorithms that(1) operate directly on mathematical structures,(2) are specified in some adequate logical formalism, and(3) respect in each computational step all symmetries of the input structure and of the current state of the computation.Such symmetry-invariant algorithms arise in such scenarios where we work with objects that are understood and treated as abstract mathematical structures (databases, knowledge bases, transition systems etc.). However, many classical algorithms (such as depth first search or Gaußian elimination) are not symmetry-invariant; they break symmetries by explicit choices out of collections of equivalent objects.What are now the consequences of the (in many cases indispensible) requirement of symmetry-invariance? Is is possible to develop computation models and algorithms that are symmetry invariant, without paying a high prize in terms of computational power and complexity?A classical incarnation of this general objective is the question whether there is a logic for polynomial time, which is generally considered as the main open problem of descriptive complexity theory. The most important current candidates for such a logic are Rank Logic and Choiceless Polynomial Time. Algorithmic problems of foremost interest in this connection come from domains such as linear algebra, permutation group theory and linear equation systems.Besides finite structures, we shall also consider finitely definable sets over infinite structures. It is important to understand the arising symmetries in such contexts.Further objectives of this project concern the expressive and computational power of symmetry-invariant computation models and logics in connection with low-level-complexity, symmetric circuits, and propositional proof systems.

该项目的中心目标是研究算法的表达能力和计算能力，这些算法（1）直接对数学结构进行操作，（2）以某种适当的逻辑形式主义指定，以及（3）在每个计算步骤中尊重输入结构和当前结构的所有对称性 这种不变量算法出现在这样的场景中，在这些场景中，我们与被理解和视为抽象数学结构的对象（数据库、知识库、转换系统等）一起工作。然而，许多经典的算法（如深度优先搜索或高斯消去法）并不是对称不变的，它们通过从等价对象的集合中进行显式选择来打破对称性。现在，对称不变的要求（在许多情况下是不可或缺的）的结果是什么？ 有没有可能开发出对称不变的计算模型和算法，而不需要在计算能力和复杂性方面付出高昂的代价？这个一般目标的一个经典体现是是否存在多项式时间逻辑的问题，这通常被认为是描述复杂性理论的主要开放问题。 目前最重要的候选人这样的逻辑是秩逻辑和无选择多项式时间。在这方面最感兴趣的数学问题来自线性代数、置换群理论和线性方程组等领域。除了有限结构，我们还将考虑无限结构上的可定义集合。重要的是要理解在这种情况下出现的对称性。这个项目的进一步目标涉及与低层次复杂性，对称电路，和命题证明系统连接的非对称计算模型和逻辑的表达和计算能力。