AI、机器学习、深度学习、数据挖掘或数学研究者您好，以下是一篇论文的标题和摘要：标题：同质性与可同质性: 对逻辑SNP的困难问题摘要：我们证明了这样一个问题是不可判定的：给定一个SNP句子，判断它是否定义了一类可同质化的有限结构，即使该句子源于连接Datalog碎片并且最多使用二进制关系符号。作为证明副产品，我们还得到了一些其他Datalog程序性质的不可判定性，例如它们是否可以在MMSNP中重写，它们是否解决了一些有限域CSP或它们是否定义了有限关系签名中一个均匀Ramsey结构的归纳年龄。接着，我们证明了有限绑定类的测试并购属性的问题是EXPSPACE-难或PSPACE-难的，具体情况取决于输入是通过通用语句还是一组被禁止的子结构来指定的。 (Homogeneity and Homogenizability: Hard Problems for the Logic SNP)

翻译：AI、机器学习、深度学习、数据挖掘或数学研究者您好，以下是一篇论文的标题和摘要：标题：同质性与可同质性: 对逻辑SNP的困难问题摘要：我们证明了这样一个问题是不可判定的：给定一个SNP句子，判断它是否定义了一类可同质化的有限结构，即使该句子源于连接Datalog碎片并且最多使用二进制关系符号。作为证明副产品，我们还得到了一些其他Datalog程序性质的不可判定性，例如它们是否可以在MMSNP中重写，它们是否解决了一些有限域CSP或它们是否定义了有限关系签名中一个均匀Ramsey结构的归纳年龄。接着，我们证明了有限绑定类的测试并购属性的问题是EXPSPACE-难或PSPACE-难的，具体情况取决于输入是通过通用语句还是一组被禁止的子结构来指定的。

Jakub Rydval

from arxiv, 29 pages, 3 figures

We show that the question whether a given SNP sentence defines a homogenizable class of finite structures is undecidable, even if the sentence comes from the connected Datalog fragment and uses at most binary relation symbols. As a byproduct of our proof, we also get the undecidability of some other properties for Datalog programs, e.g., whether they can be rewritten in MMSNP, whether they solve some finite-domain CSP, or whether they define the age of a reduct of a homogeneous Ramsey structure in a finite relational signature. We subsequently show that the closely related problem of testing the amalgamation property for finitely bounded classes is EXPSPACE-hard or PSPACE-hard, depending on whether the input is specified by a universal sentence or a set of forbidden substructures.

翻译：同质性与可同质性：逻辑SNP的硬问题摘要：我们展示了这样一个问题是不可判定的：给定一个 SNP 句子，判断它是否定义了一类可同质化的有限结构，即使该句子源于连接 Datalog 碎片并且最多使用二进制关系符号。作为证明副产品，我们还得到了一些其他 Datalog 程序性质的不可判定性，例如它们是否可以在 MMSNP 中重写，它们是否解决了一些有限域 CSP 或它们是否定义了有限关系签名中一个均匀 Ramsey 结构的归纳年龄。接着，我们证明了有限绑定类的测试并购属性的问题是 EXPSPACE 难或 PSPACE 难的，具体情况取决于输入是通过通用语句还是一组被禁止的子结构来指定的。