发帖
雷达卡
摘要翻译：
数量级推理--通过粗略比较量的大小进行推理--通常被称为“包络后面的计算”，其含义是计算虽然近似，但很快。本文展示了一类有趣的约束集，其中数量级推理是明显快速的。具体地说，我们提出了一个多项式时间算法，它可以解决一组形式为“a点和b点比c点和D点靠近得多”的约束。我们证明，如果把“更紧密地联系在一起”解释为无限尺度差或有限尺度差，只要尺度差大于约束集中的变量数，这种算法就可以应用。我们还证明了这类约束下的一阶理论是可判定的。
---
英文标题：
《Order of Magnitude Comparisons of Distance》
---
作者：
E. Davis
---
最新提交年份：
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中的材料。
--
---
英文摘要：
Order of magnitude reasoning - reasoning by rough comparisons of the sizes of quantities - is often called 'back of the envelope calculation', with the implication that the calculations are quick though approximate. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form 'Points a and b are much closer together than points c and d.' We prove that this algorithm can be applied if `much closer together' is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.
---
PDF链接：
https://arxiv.org/pdf/1105.5448
京公网安备 11010802022788号
