权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Homogeneous structures, constraint satisfaction problems, and topological clones

同质结构、约束满足问题和拓扑克隆

基本信息

批准号：
280296726
负责人：
Professor Dr. Manuel Bodirsky
金额：
--
依托单位：
Institut für Algebra
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2015
资助国家：
德国
起止时间：
2014-12-31 至 2018-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/280296726?language=en
关键词：
Homogeneous structures constraint satisfaction problems

项目摘要

Clones are a generalisation of groups that are of central importance in universal algebra. In the last 15 years they became an important tool for studying the computational complexity of constraint satisfaction problems (CSPs). For CSPs on infinite domains, we have to study function clones on infinite domains; those are naturally equipped with the topology of pointwise convergence. This topology makes them to topological clones, in the same way as the topological groups that arise from permutation groups with respect to the pointwise convergence topolgy. If the relations of a CSP have an omega-categorical first-order theory, then the computational complexity of the CSP only depends on the topological polymorphism clone of those relations. This includes all relations that are first-order definable over homogeneous structures with finite relational signature, and the corresponding class of CSPs is very large and contains many natural computational problems that have been studied in various areas of theoretical computer science. An important method to study polymorphism clones of those relations is Ramsey theory. The goal of this project is to investigate the interplay of topological and algebraical properties of topological clones, in particular for the questions that are of relevance for the mentioned application for the complexity of CSPs. We also want to further develop the Ramsey methods for these investigations.

克隆群是群的一种推广，在泛代数中具有核心重要性。在过去的15年里，它们成为研究约束满足问题（CSP）计算复杂性的重要工具。对于无限域上的CSP，我们必须研究无限域上的函数克隆;这些函数克隆自然具有逐点收敛的拓扑。这种拓扑使它们成为拓扑克隆，就像拓扑群从关于逐点收敛拓扑的置换群中产生一样。如果CSP的关系具有Ω范畴一阶理论，则CSP的计算复杂度仅取决于这些关系的拓扑多态克隆。这包括所有的关系，是一阶定义的同构结构与有限的关系签名，相应的类CSP是非常大的，并包含许多自然的计算问题，已经研究了在理论计算机科学的各个领域。Ramsey理论是研究这些关系的多态性克隆的一个重要方法。该项目的目标是研究拓扑克隆的拓扑和代数性质的相互作用，特别是对于与所述CSP复杂性应用相关的问题。我们还希望进一步发展拉姆齐方法进行这些调查。