Descriptive Complexity with Algebraic Operators

使用代数运算符描述复杂性

• 批准号: EP/H026835/1
• 负责人: Anuj Dawar
• 金额: $ 54.13万
• 依托单位: University of Cambridge
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2010
• 资助国家: 英国
• 起止时间: 2010 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FH026835%2F1
• 关键词: Descriptive; Complexity; Algebraic; Operators

The study of computational complexity is concerned with understanding what makes certain computational tasks inherently difficult to solve. In this context, problems that can be solved by means of algorithms that take a number of steps bounded by a polynomial are considered to be feasible, or efficiently solvable. A long standing research concern in the field of descriptive complexity has been to give a complete classification of those problems that are feasible. Such a complete classification would take the form of a formal language (or a logic) in which one could define all the feasible problems, but no others. It has been known for some time that languages based on induction and counting are not sufficient for this purpose and it has recently been discovered that adding certain operators based on linear algebra can extend the power of such languages. Our research aims at building on this breakthrough by understanding the power of these extended languages. To do this we will develop new methods to analyse the expressive power and use this to determine whether or not the newly defined languages do capture the power of feasible computation.We will also investigate whether these languages capture feasible computation in interesting special cases.

计算复杂性的研究关注于理解是什么使得某些计算任务固有地难以解决。在这种情况下，可以通过采取由多项式限定的多个步骤的算法来解决的问题被认为是可行的，或者是有效可解的。描述复杂性领域的一个长期研究关注的问题是对那些可行的问题进行完整的分类。这样一个完整的分类将采取形式语言（或逻辑）的形式，在这种形式语言中，人们可以定义所有可行的问题，但不能定义其他问题。一段时间以来，人们已经知道，基于归纳和计数的语言不足以实现这一目的，最近发现，添加某些基于线性代数的运算符可以扩展这些语言的功能。我们的研究旨在通过理解这些扩展语言的力量来实现这一突破。为此，我们将开发新的方法来分析表达能力，并使用它来确定新定义的语言是否确实捕获了可行计算的能力，我们还将研究这些语言是否在有趣的特殊情况下捕获了可行计算。

项目成果

Solving Linear Programs without Breaking Abstractions

在不破坏抽象的情况下求解线性规划

• DOI: 10.1145/2822890
• 发表时间: 2015
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Anderson M

Maximum Matching and Linear Programming in Fixed-Point Logic with Counting

带计数的定点逻辑中的最大匹配和线性规划

• DOI: 10.1109/lics.2013.23
• 发表时间: 2013
• 作者: Anderson M

Automata, Languages, and Programming

自动机、语言和编程

• DOI: 10.1007/978-3-642-39212-2_44
• 发表时间: 2013
• 作者: Christodoulou G

Degree lower bounds of tower-type for approximating formulas with parity quantifiers.

用于使用奇偶量词近似公式的塔式下限。

• DOI: 10.17863/cam.71022
• 发表时间: 2014
• 作者: Atserias A

On Symmetric Circuits and Fixed-Point Logics

对称电路和定点逻辑

• DOI: 10.1007/s00224-016-9692-2
• 发表时间: 2016
• 期刊: Theory of Computing Systems
• 影响因子: 0.5
• 作者: Anderson M