• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Complexity Classifications for Propositional Abduction in Post's Framework
【24h】

Complexity Classifications for Propositional Abduction in Post's Framework

机译：邮政框架中命题绑架的复杂性分类

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this article, we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behaviour, it aims at finding an explanation for some observed manifestation. In this article, we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be Incomplete in general. We focus on formulas in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants, we obtain a complexity classification for all possible sets of Boolean functions. In this way, we identify easier cases, namely NP-complete, coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting the sources of intractability. Further, we address the problem of counting the full explanations and prove a trichotomous classification theorem.
机译：在本文中，我们研究了绑架的复杂性，绑架是非单调推理的基本和重要形式。给定一个解释世界行为的知识库，它的目的是找到某种观察到的表现形式的解释。在本文中，我们考虑命题绑架，其中知识库和表现形式由命题公式表示。通常，判断是否存在解释的问题是不完整的。我们关注的公式中，允许的连接词取自某些布尔函数集。在限制表现形式和假设时，我们考虑了绑架问题的不同变体。对于所有这些变体，我们为所有可能的布尔函数集获得了复杂度分类。这样，我们确定了更简单的情况，即NP-完全，coNP-完全和多项式情况。因此，我们详细了解了命题绑架问题的复杂性，从而突出了难治性的根源。此外，我们解决了计算全部解释的问题，并证明了三分类分类定理。

著录项

  • 来源
    《Journal of logic and computation》 |2012年第5期|p.1145-1170|共26页
  • 作者

    NADIA CREIGNOU; JOHANNES SCHMIDT; MICHAEL THOMAS;

  • 作者单位

    Laboratoire d'Informatique Fondamentale, Unite Mixte de Recherche, Centre National de Recherche scientifique, 6166, Aix-Marseille Universite, 163 Avenue de Luminy, 13288 Marseille Cedex 9, France;

    Laboratoire d'Informatique Fondamentale, Unite Mixte de Recherche, Centre National de Recherche scientifique, 6166, Aix-Marseille Universite, 163 Avenue de Luminy, 13288 Marseille Cedex 9, France;

    TWT GmbH, Bernhaeuser Strasse 40-42, Neuhausen auf den Fildern, 73765, Germany;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    abduction; computational complexity; post's lattice; propositional logic; boolean connective;

    机译：绑架计算复杂度;邮政的格子;命题逻辑;布尔连接词;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号