...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theory and Practice of Logic Programming >Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
【24h】

Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs

机译：三分法和二分法导致析取逻辑程序的推理复杂性

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

摘要

We present trichotomy results characterizing the complexity of reasoning with disjunctive logic programs. To this end, we introduce a certain definition schema for classes of programs based on a set of allowed arities of rules. We show that each such class of programs has a finite representation, and for each of the classes definable in the schema, we characterize the complexity of the existence of an answer set problem. Next, we derive similar characterizations of the complexity of skeptical and credulous reasoning with disjunctive logic programs. Such results are of potential interest. On the one hand, they reveal some reasons responsible for the hardness of computing answer sets. On the other hand, they identify classes of problem instances, for which the problem is "easy" (in P) or "easier than in general" (in NP). We obtain similar results for the complexity of reasoning with disjunctive programs under the supported-model semantics.
机译：我们提出了三分法结果，表征了析取逻辑程序推理的复杂性。为此，我们基于一组允许的规则集合为程序类引入某种定义模式。我们表明，程序的每个此类都有一个有限的表示形式，并且对于模式中可定义的每个类别，我们都描述了答案集问题存在的复杂性。接下来，我们使用析取逻辑程序得出怀疑和轻率推理的复杂性的类似特征。这样的结果可能引起人们的兴趣。一方面，他们揭示了导致答案集难以计算的一些原因。另一方面，他们确定问题实例的类别，对于这些实例，问题是“容易”（在P中）或“比一般情况下更容易”（在NP中）。对于在支持模型语义下使用析取程序进行推理的复杂性，我们获得了相似的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号