Abstract Minimal model and partial implication semantics play important roles in the subfields of artificial intelligence. In this paper, the complexity issues of minimal model and partial implication semantics are analyzed when the antecedent and the consequent are literals, literal sets and formulas respectively. The results show that the complexities of minimal model and partial implication semantics increase when the antecedent and consequent become more complex. Moreover, the complexities of all these decision problems lie in the first two layers of polynomial hierarchy.
[1] van der Hoek W, Wooldrige W. Towards a Logic of Rational Agen
cy. Logic Journal of the IGPL, 2003, 11(2): 133-157 [2] Shi Zhongzhi. Intelligent Agent and Its Application. Beijing, Chi na: Science Press, 2000 (in Chinese)摇摇(史忠植. 智能主体及其应用. 北京:科学出版社, 2000)7 9 5 5 期摇摇摇摇周熠等:部分蕴涵复杂性分析 [3] Hu Shanli, Shi Chunyi. An Intention Model for Agent. Journal of Software, 2000, 11(7): 965-970 (in Chinese)摇摇(胡山立,石纯一. Agent 的意图模型. 软件学报, 2000, 11(7):965-970) [4] Mao Xinjun, Wang Huaiming, Chen Huowang, et al. The Intention Theory of Agent Computing in Multi-Agent System. Journal of Soft
ware, 1999, 10(1): 43-48 (in Chinese)摇摇(毛新军,王怀民,陈火旺,等. Agent 在多Agent 系统中计算的意愿理论. 软件学报, 1999, 10(1): 43-48) [5] Rao A S, Georgeff M P. Modeling Rational Agents within a BDI-Ar chitecture / / Proc of the 2nd International Conference on Principles of Knowledge Representation and Reasoning. San Mateo, USA:Morgan Kaufmann, 1991: 473-484 [6] Zhao Xinyu, Lin Zuoquan. Modeling Belief, Capability and Promise for Cognitive Agents-A Modal Logic Approach / / Proc of the 1st In ternational Conference on Natural Computation. Changsha, China,
2005: 825-834 [7] Lang J, Liberatore P, Marquis P. Propositional Independence -For
mula-Variable Independence and Forgetting. Journal of Artificial In telligence Research, 2003, 18: 391-443 [8] Lakemeyer G. Relevance from an Epistemic Perspective. Artificial Intelligence, 1997, 97(1/2): 137-167 [9] Marquis P. Novelty Revisited / / Proc of the 6th International Sym posium on Methodologies for Intelligent System. Charlotte, USA,1991: 550-559 [10] Eiter T, Gottlob G. The Complexity of Logic-Based Abduction. Journal of ACM, 1995, 42(1): 3-42 [11] Chen Rong, Jiang Yunfei, Lin Li. Study of Abductive Reasoning:State of the Art and Problems. Computer Science, 2003, 30(5):23-25,36 (in Chinese)摇摇(陈荣,姜云飞,林笠. 溯因推理研究:现状与问题. 计算机科学,2003, 30(5): 23-25,36) [12] Zhou Yi, Chen Xiaoping. Partial Implication Semantics for Desira ble Propositions / / Proc of the 9th International Conference on Prin ciples of Knowledge Representation and Reasoning. Whistler, Cana
da, 2004: 606-611 [13] Zhou Yi, Chen Xiaopin. Implicit Desire and Its Formalization.
Journal of Software, 2005, 16(5): 771-778 (in Chinese)摇摇(周熠,陈小平. 隐式愿望及其形式化. 软件学报, 2005, 16(5): 771-778) [14] Papadimitriou C H. Computational Complexity. New York, USA:Addison-Wesley, 1994
2007, Vol. 20 
