摘要翻译：
在最近的人工智能文献中，对于用于表示时间和空间知识的各种定性关系代数，对代数子集推理问题的计算复杂度进行了深入的研究。这些研究的主要目的是描述一个限制的极大可处理子代数集，理想地以关于宿主代数的穷举方式描述。本文引入了一个新的空间同余推理代数，证明了空间代数MC-4中的可满足性问题是NP-完全的，并给出了该代数中可处理性的一个完全分类，该分类是基于三个最大可处理子类的个体化，其中一个子类包含基本关系。这三个代数是由16个关系中的14个、10个和9个关系组成的，这些关系构成了全代数。
---
英文标题：
《The Complexity of Reasoning about Spatial Congruence》
---
作者：
M. Cristani
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras. In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.
---
PDF链接：
https://arxiv.org/pdf/1106.0664