기술 요약: $\mathcal{EL}^\bot$의 수선 의미론(Repair Semantics) 하에서 속성 결합을 통한 ABox 추론(Abduction)

문제 정의

본 논문은 수선 의미론(repair semantics) 하에서의 기술 논리(특히 $\mathcal{EL}^\bot$) 내 ABox 추론(ABox abduction) 문제를 다룬다. 추론(Abduction)이란 모순이 있는 지식 베이스 $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$에 가설(가설 집합 $\mathcal{H}$)을 추가하여, 누락된 함의(관찰) $\alpha$를 참으로 만드는 가설을 찾는 과정을 의미한다.

수선 의미론의 맥락에서, 모순은 "수선"(ABox의 극대 일관 부분 집합)을 고려함으로써 처리된다. 본 논문은 두 가지 특정 의미론에 집중한다:

1. 용기 의미론(Brave Semantics): $\alpha$가 적어도 하나의 수선에서 성립하면 함의된다.
2. AR (All Repairs) 의미론: $\alpha$가 모든 수선에서 성립하면 함의된다.

기존 연구[17]는 개별적인 바람직한 속성들(예: 비자명성, 시그니처 제한, 충돌 격리, 그리고 다양한 최소성 기준)에 대한 추론의 계산 복잡도를 조사하였다. 본 논문은 이러한 속성들의 결합을 조사한다. 핵심 연구 질문은 가설이 여러 속성을 동시에 만족하도록 요구하는 것(예: 비자명하면서 동시에 충돌을 격리하거나, 부분 집합 최소이면서 동시에 시그니처가 제한된 경우)이, 각 속성을 개별적으로 만족할 때와 비교하여 계산 복잡도를 증가시키는지 여부이다.

방법론

저자들은 속성의 결합에 대한 두 가지 근본적인 추론 문제의 계산 복잡도를 분석한다:

1. 존재 문제(Existence Problem): 주어진 속성들을 만족하는 가설이 존재하는가?
2. 검증 문제(Verification Problem): 주어진 ABox $\mathcal{H}$가 속성들을 만족하며 유효한 가설을 구성하는가?

본 연구는 다음의 조합을 다룬다:

• 기본 속성:
  • 비자명성(Non-triviality): 가설이 관찰 $\alpha$를 포함하지 않는다.
  • 시그니처 제한($\Sigma$-restricted): 가설이 지정된 시그니처의 기호만을 사용한다.
  • 충돌 격리(Conflict-confining): 가설이 $\mathcal{K}$에 이미 존재하는 것 이상의 새로운 충돌을 도입하지 않는다.
• 최소성 기준:
  • 부분 집합 최소성($\subseteq$-minimal): 가설의 진부분 집합 중 유효한 가설이 존재하지 않는다.
  • 카디널리티 최소성($\leq$-minimal): 더 적은 수의 단언(assertion)을 가진 가설이 유효하지 않다.
  • 충돌 최소성($\subseteq_c$-minimal): 가설이 엄격하게 더 작은 집합의 충돌을 도입하지 않는다.

분석은 표준 복잡도 클래스($\text{P}, \text{NP}, \text{coNP}, \text{DP}, \Sigma^P_2, \Pi^P_2$)에 의존하며, 하한(lower bounds)을 설정하기 위해 알려진 어려운 문제들(예: QBF 타당성, 함의/비함의 조합)로부터 환원(reduction)을 사용하고, 상한(upper bounds)을 설정하기 위해 오라클 호출을 포함한 guess-and-check 알고리즘을 사용한다.

주요 기여 및 결과

1. 기본 속성의 결합 (비-최소성)

본 논문은 기본 속성들을 결합하는 것이 일반적으로 개별 속성의 최고 복잡도를 넘어 복잡도를 증가시키지 않는다는 것을 보여준다.

• $\Sigma$-제한 + 비자명성: Brave 의미론에서는 $\text{NP}$-완전성을 유지하며, AR 의미론에서는 $\Sigma^P_2$-완전성을 유지한다.
• 충돌 격리 + 비자명성 / $\Sigma$-제한: 복잡도가 두 의미론 모두에서 $\Sigma^P_2$-완전성으로 증가한다. 이는 충돌 격리 가설 단독으로는 Brave에서 $\Sigma^P_2$-완전이지만 AR에서는 $\text{coNP}$-완전인 것과 대조되는 주목할 만한 결과로, 비자명성이나 시그니처 제한을 추가하면 AR 복잡도가 Brave의 경우와 일치하도록 높아진다.

2. 부분 집합 최소성($\subseteq$-minimality)과의 결합

• 부분 집합 최소 + 비자명 / $\Sigma$-제한: 복잡도는 부분 집합 최소 가설을 검증하는 것의 복잡도와 일치한다 (Brave에서는 $\text{DP}$-완전, AR에서는 $\Pi^P_2$-완전).
• 부분 집합 최소 + 충돌 격리:
  • Brave 의미론: $\text{DP}$-완전.
  • AR 의미론: 복잡도는 $\Pi^P_2$에 속하며 $\text{coNP}$-하한을 가지지만, 정확한 상한은 여전히 미해결 상태이다.

3. 카디널리티 최소성($\leq$-minimality)과의 결합

부분 집합 최소성과 달리, 카디널리티 최소성은 다른 속성들과 결합될 때 종종 복잡도를 증가시키는데, 이는 주로 비자명성이나 시그처 제한에 의해 자명한 가설(크기 1)이 허용되지 않기 때문이다.

• $\leq$-최소 + 비자명 / $\Sigma$-제한: 복잡도가 Brave에서는 $\text{DP}$-완전, AR에서는 $\Pi^P_2$-완전으로 증가한다.
• $\leq$-최소 + 충돌 격리:
  • Brave 의미론: $\Pi^P_2$-완전.
  • AR 의미론: $\text{coNP}$-완전 (Lemma 6에 의해, AR의 경우 존재성이 자명한 가설이 충돌 격리임을 함의하므로 변화 없음).

4. 충돌 최소성($\subseteq_c$-minimality)과의 결합

• $\subseteq_c$-최소 + 비자명 / $\Sigma$-제한: 복잡도는 Brave와 AR 모두에서 $\Pi^P_2$-완전이다.
• 본 논문은 이러한 결과들을 카디널리티 충돌 최소성($\leq_c$)으로 확장하는 것이 어려울 수 있다고 언급하는데, 이는 작은 가설이 지수적으로 많은 새로운 충돌을 유발할 가능성 때문이며, 이는 $\#\text{P}$-경직성(hardness)을 암시한다.

의의 및 주장

본 논문의 주요 관찰 결과는 가설에 추가적인 속성을 요구하는 것이 (카디디널리티나 충돌 수를 포함하는 최소성 기준이 아닌 한) 복잡도를 증가시키지 않는 경우가 많다는 것이다.

• 주요 발견: 대부분의 기본 속성(비자명성, 시그니처 제한, 충돌 격리) 및 부분 집합 최소성의 결합에 대해, 복잡도는 관련된 개별 속성 중 가장 "높은" 복잡도에 의해 결정된다.
• 예외: 카디널리티-최소성 또는 충돌-최소성을 포함하는 결합은 빈번하게 더 높은 복잡도 클래스(예: $\text{coNP}$에서 $\Pi^P_2$ 또는 $\text{DP}$로 이동)로 이어진다.
• 범위: 결과는 $\mathcal{EL}^\bot$의 Brave 및 AR 의미론에 국한된다. 저자들은 더 표현력이 높은 논리(예: $\mathcal{ALC}$)의 경우, 복잡도가 함의 문제 자체(ExpTime)에 의해 지배될 것이므로 이러한 특정 추론의 구분이 덜 중요해질 것이라고 언급한다.
• 향후 연구: 저자들은 열린 간극을 식별하였다. 구체적으로 $\subseteq$-최소 충돌 격리 AR-가설의 정확한 복잡도, 그리고 $\text{DL-Lite}$에서의 조합의 복잡도 지형(구조적 특성 덕분에 충돌 격리가 문제를 단순화할 것으로 예상됨), 그리고 IAR 의미론 하에서의 복잡도이다.

본 논문은 가설에 대한 추가적인 속성을 요구하는 것이 (최소적이면서 동시에 충돌을 격리하는 설명을 생성하는 것과 같은 실용적 응용을 위해) 바람직하지만, 이것이 가장 흔한 조합들에 대해 반드시 계산적 불가능성(intractability)의 증가를 수반하는 것은 아니라고 결론짓는다.