Epistemic Logic Programs: Non-Ground and Counting Complexity
Created by
- Haebom
Category
Empty
저자
Thomas Eiter, Johannes K. Fichte, Markus Hecher, Stefan Woltran
개요
본 논문은 Answer Set Programming (ASP)의 확장판인 Epistemic Logic Programs (ELP)의 복잡도를 연구합니다. ELP는 ASP의 여러 해답 집합(answer sets)을 고려하여 추론하며, 이러한 해답 집합들의 모임을 world view라고 합니다. 기존 연구는 주로 명제 논리 프로그램의 복잡도에 집중했지만, 본 논문은 비명제(non-ground) ELP의 복잡도를 체계적으로 분석합니다. 잘 알려진 프로그램 조각들에 대한 복잡도를 NEXPTIME과 Σ^P_2 오라클에 대한 접근성을 이용한 완전성까지 포괄적으로 규명하고, 정량적 측면에서는 #EXP를 넘어서는 계산 복잡도 결과를 제시합니다. 높은 복잡도를 완화하기 위해, 술어의 arity가 제한된 경우에 대한 결과를 제시하며, 다항 계층의 네 번째 수준까지 도달합니다. 마지막으로, 매개변수 트리 너비에 대한 ETH-tight 실행 시간 결과를 제시하는데, 이는 epistemic literal의 (주변) 확률에 대한 추론을 포함하는 정량적 추론에 응용될 수 있습니다.
시사점, 한계점
•
시사점: 비명제 ELP의 복잡도에 대한 포괄적인 이해를 제공하여, ELP 기반 시스템의 설계 및 최적화에 중요한 기반을 마련합니다. 특히, 제한된 술어 arity 하에서의 복잡도 분석은 실용적인 응용에 중요한 시사점을 제공합니다. 트리 너비를 매개변수로 한 실행 시간 분석은 정량적 추론 분야에 적용 가능성을 높입니다.
•
한계점: 본 논문은 주로 이론적인 복잡도 분석에 초점을 맞추고 있으며, 실제 ELP 시스템에 대한 실험적인 평가는 제시되지 않았습니다. 더욱 광범위한 프로그램 조각이나 실제 응용 문제에 대한 복잡도 분석이 추가적으로 필요할 수 있습니다.
