含凸抽象约束的逻辑程序复杂性

作     者：王翔龙 王以松 谢仲涛 

作者机构：公共大数据国家重点实验室贵州大学计算机科学与技术学院 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2025年

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目资助(62376066,61976065) 贵州省科技计划项目(黔科合支撑一般-259) 

主　　题：回答集编程 凸抽象约束 回答集语义 基本逻辑程序 计算复杂性 

摘      要：基于回答集语义的逻辑程序（简称ASP ）是描述性问题求解的典范，广泛应用于规划、诊断、调度以及生物信息学等领域，为了增强ASP 的表达能力，ASP 引入了数据库系统中的聚合函数约束，并提出了SPT 、FLP 等语义，抽象约束剥离聚合函数约束的具体形式成为研究ASP 语义等性质的重要工具，并得到了抽象约束逻辑程序的各种回答集语义之间的关系和复杂性问题等的相关结果。本文进一步研究了仅含凸抽象约束原子抽象约束逻辑的性质，证明了仅含凸抽象约束原子的正规逻辑程序判定是否存在FLP 回答集是∑2p完全的，其审慎推理和大胆推理分别是Π2p完全的和∑2p完全的。这些复杂性结果进一步理清了各类逻辑程序间的表达能力关系，为设计有效的回答集求解器提供了新的思路，也为进一步探索ASP在解决用凸抽象约束表示的问题中的应用提供了理论基础。