결정 가능성과 NP-Hard 문제 (Decidability and NP-Hard Problems)
1. 개요
AI 플래닝 문제의 결정 가능성(decidability)과 난이도(hardness)는 표현 언어의 표현력에 따라 결정된다. STRIPS 수준에서는 PSPACE-complete로 결정 가능하나, 수치적 기능이나 HTN의 일반적 형태에서는 결정 불가능해질 수 있다.
2. 결정 가능성
| 표현 수준 | 결정 가능성 |
|---|---|
| 명제적 STRIPS | 결정 가능 (PSPACE-complete) |
| ADL | 결정 가능 |
| 제한된 수치 | 결정 가능 |
| 일반 수치 | 결정 불가능 |
| HTN (일반) | 결정 불가능 |
| HTN (비재귀적) | 결정 가능 (NEXPTIME) |
3. NP-Hard 문제와의 관계
제한된 길이의 계획 존재 판정은 NP-complete이며, 최적 계획 탐색은 NP-hard이다. 이는 다항 시간 알고리즘이 존재하지 않을 가능성을 시사한다.
4. 참고 문헌
- Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” AI, 69, 165-204.
| 버전 | 날짜 | 변경 사항 |
|---|---|---|
| v0.1 | 2026-04-05 | 초안 작성 |