PYI: Characterization of Tractable Sub-Problems in Automated Reasoning

这是五年PYI持续奖励的第一年基本资金。这项工作将扩展对可处理的推理模型的理解和利用。为了解释人们如何在理论上难以处理的任务上表现得如此出色，我们必须假设基于可处理模型的近似方法涵盖了智能活动的重要部分，因此，应该作为自动推理系统的基石。这一原理为本研究提供了动力。这项工作将：(1)为连接主义模型和神经网络建立一个正式的关系基础，并使用约束网络的语言，在表达能力和计算效率方面量化这些模型的能力和局限性。(2)使用关系代数和（有向）约束网络的语言建立因果理论的形式化基础。(3)识别可处理的逻辑程序类、默认知识库和时间推理子语言，通过其规范的拓扑特征进行识别。(4)将约束网络技术应用于调度、计划和诊断等现实生活问题。

This is the first year base amount funding of a five year PYI continuing award. This work will expand on the understanding and exploitation of tractable models of reasoning. To explain how people perform so well on tasks that are theoretically intractable, we must assume that approximation methods, based on tractable models, cover a significant part of intelligent activities and, hence, should serve as the cornerstone of automated reasoning systems. This principle provides the motivation for this research. This work will: (1) Establish a formal relational basis for connectionist models and neural networks and, using the language of constraint networks, quantify the powers and limitations of these models in terms of expressiveness and computational efficiency. (2) Establish a formal basis of causal theories using the language of relational algebra and (directed) constraint networks. (3) Identify tractable classes of logic programs, default knowledge bases and temporal reasoning sub-languages, recognizable via the topological features of their specifications. (4) Apply constraint network techniques to real life problems such as scheduling, planning and diagnosis.