Technisches Resümee: Kombination von Eigenschaften für die ABox-Abduktion unter Repair-Semantik für $\mathcal{EL}^\bot$

Problemstellung

Das Paper adressiert das ABox-Abduktionsproblem innerhalb der Deskriptionslogiken (speziell $\mathcal{EL}^\bot$) unter Repair-Semantik. Abduktion zielt darauf ab, eine Hypothese (eine Menge von Assertions $\mathcal{H}$) zu finden, die, wenn sie zu einer inkonsistenten Wissensbasis $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ hinzugefügt wird, eine fehlende Folgerung (Observation) $\alpha$ wahr macht.

Im Kontext der Repair-Semantik werden Inkonsistenzen durch die Betrachtung von „Repairs“ (maximal konsistente Teilmengen der ABox) behandelt. Das Paper konzentriert sich auf zwei spezifische Semantiken:

1. Brave Semantics: $\alpha$ ist gefolgert, wenn sie in mindestens einem Repair gilt.
2. AR (All Repairs) Semantics: $\alpha$ ist gefolgert, wenn sie in allen Repairs gilt.

Während vorangegangene Arbeiten [17] die Komplexität der Abduktion für einzelne wünschenswerte Eigenschaften (z. B. Nicht-Trivialität, Signaturbeschränkung, Konflikt-Einschränkung und verschiedene Minimalitätskriterien) untersuchten, untersucht dieses Paper die Kombinationen dieser Eigenschaften. Die zentrale Forschungsfrage ist, ob die Anforderung, dass eine Hypothese mehrere Eigenschaften gleichzeitig erfüllen muss (z. B. sowohl nicht-trivial als auch konflikt-beschränkend zu sein, oder Teilmengen-minimal und signatur-beschränkt zu sein), zu einer Erhöhung der Rechenkomplexität im Vergleich zur Erfüllung derselben in Isolation führt.

Methodik

Die Autoren analysieren die Rechenkomplexität zweier grundlegender Reasoning-Probleme für Kombinationen von Eigenschaften:

1. Existenzproblem: Existiert eine Hypothese, welche die gegebenen Eigenschaften erfüllt?
2. Verifikationsproblem: Erfüllt eine gegebene ABox $\mathcal{H}$ die Eigenschaften und stellt eine gültige Hypothese dar?

Die Untersuchung umfasst Kombinationen von:

• Basiseigenschaften:
  • Nicht-Trivialität: Die Hypothese enthält nicht die Observation $\alpha$.
  • Signaturbeschränkung ($\Sigma$-beschränkt): Die Hypothese verwendet nur Symbole aus einer spezifizierten Signatur.
  • Konflikt-Beschränkung (Conflict-confining): Die Hypothese führt keine neuen Konflikte über die bereits in $\mathcal{K}$ vorhandenen hinaus ein.
• Minimalitätskriterien:
  • Teilmengen-Minimalität ($\subseteq$-Minimalität): Keine echte Teilmenge der Hypothese ist eine gültige Hypothese.
  • Kardinalitäts-Minimalität ($\leq$-Minimalität): Keine Hypothese mit weniger Assertions ist gültig.
  • Konflikt-Minimalität ($\subseteq_c$-Minimalität): Keine Hypothese führt eine strikt kleinere Menge an Konflikten ein.

Die Analyse stützt sich auf Standard-Komplexitätsklassen ($\text{P}, \text{NP}, \text{coNP}, \text{DP}, \Sigma^P_2, \Pi^P_2$) und verwendet Reduktionen von bekannten harten Problemen (z. B. QBF-Gültigkeit, Entailment/Non-Entailment-Kombinationen), um untere Schranken zu etablieren, sowie Guess-and-Check-Algorithmen mit Oracle-Aufrufen, um obere Schranken zu bestimmen.

Zentrale Beiträge und Ergebnisse

1. Kombinationen von Basiseigenschaften (Nicht-Minimalität)

Das Paper zeigt, dass die Kombination von Basiseigenschaften im Allgemeinen nicht über die höchste Komplexität der einzelnen Eigenschaften hinaus ansteigt.

• $\Sigma$-Beschränkung + Nicht-Trivialität: Die Komplexität bleibt $\text{NP}$-vollständig für Brave Semantics und $\Sigma^P_2$-vollständig für AR Semantics.
• Konflikt-Beschränkung + Nicht-Trivialität / $\Sigma$-Beschränkung: Die Komplexität steigt auf $\Sigma^P_2$-vollständig für beide Semantiken (Brave und AR). Dies ist ein bemerkenswertes Ergebnis, da alleinige konflikt-beschränkende Hypothesen $\Sigma^P_2$-vollständig für Brave, aber nur $\text{coNP}$-vollständig für AR sind; das Hinzufügen von Nicht-Trivialität oder Signaturbeschränkung hebt die AR-Komplexität auf das Niveau des Brave-Falls.

2. Kombinationen mit Teilmengen-Minimalität ($\subseteq$-Minimalität)

• Teilmengen-minimal + Nicht-Trivial / $\Sigma$-beschränkt: Die Komplexität entspricht der Verifikation alleiniger Teilmengen-minimaler Hypothesen ($\text{DP}$-vollständig für Brave, $\Pi^P_2$-vollständig für AR).
• Teilmengen-minimal + Konflikt-beschränkt:
  • Für Brave Semantics: $\text{DP}$-vollständig.
  • Für AR Semantics: Die Komplexität liegt in $\Pi^P_2$ und ist $\text{coNP}$-hart, aber die präzise obere Schranke bleibt offen.

3. Kombinationen mit Kardinalitäts-Minimalität ($\leq$-Minimalität)

Im Gegensatz zur Teilmengen-Minimalität führt die Kardinalitäts-Minimalität oft zu einer erhöhten Komplexität, wenn sie mit anderen Eigenschaften kombiniert wird, primär weil die triviale Hypothese (Größe 1) oft durch Nicht-Trivialität oder Signaturbeschränkungen ausgeschlossen wird.

• $\leq$-minimal + Nicht-Trivial / $\Sigma$-beschränkt: Die Komplexität steigt auf $\text{DP}$-vollständig für Brave und $\Pi^P_2$-vollständig für AR.
• $\leq$-minimal + Konflikt-beschränkt:
  • Für Brave Semantics: $\Pi^P_2$-vollständig.
  • Für AR Semantics: $\text{coNP}$-vollständig (bleibt unverändert gegenüber dem Einzelfall aufgrund von Lemma 6, welches besagt, dass für AR die Existenz impliziert, dass die triviale Hypothese konflikt-beschränkt ist).

4. Kombinationen mit Konflikt-Minimalität ($\subseteq_c$-Minimalität)

• $\subseteq_c$-minimal + Nicht-Trivial / $\Sigma$-beschränkt: Die Komplexität ist $\Pi^P_2$-vollständig für sowohl Brave als auch AR Semantics.
• Das Paper merkt an, dass die Erweiterung dieser Ergebnisse auf die Kardinalitäts-Konflikt-Minimalität ($\leq_c$) schwierig ist, da eine kleine Hypothese potenziell exponentiell viele neue Konflikte auslösen kann, was auf eine potenzielle $\#\text{P}$-Härte hindeutet.

Bedeutung und Behauptungen

Die Hauptbeobachtung des Papers ist, dass das Hinzufügen zusätzlicher Eigenschaften für Hypothesen oft nicht zu einer Erhöhung der Komplexität führt, sofern es sich nicht um Minimalitätskriterien handelt, die Kardinalität oder Konfliktanzahlen betreffen.

• Hauptergebnis: Für die meisten Kombinationen von Basiseigenschaften (Nicht-Trivialität, Signaturbeschränkung, Konflikt-Beschränkung) und der Teilmengen-Minimalität wird die Komplexität durch die „höchste“ Komplexität der beteiligten Einzel-Eigenschaften bestimmt.
• Ausnahme: Kombinationen, die Kardinalitäts-Minimalität oder Konflikt-Minimalität beinhalten, führen häufig zu höheren Komplexitätsklassen (z. B. der Übergang von $\text{coNP}$ zu $\Pi^P_2$ oder $\text{DP}$).
• Geltungsbereich: Die Ergebnisse sind spezifisch für $\mathcal{EL}^\bot$ unter Brave und AR Semantics. Die Autoren merken an, dass für ausdrucksstärkere Logiken (wie $\mathcal{ALC}$) die Komplexität wahrscheinlich durch das Entailment-Problem selbst (ExpTime) dominiert wird, was diese spezifischen Abduktions-Unterschiede weniger bedeutsam macht.
• Zukünftige Arbeit: Die Autoren identifizieren offene Lücken, insbesondere die präzise Komplexität für $\subseteq$-minimale, konflikt-beschränkende AR-Hypothesen sowie die Komplexitätslandschaft für Kombinationen in $\text{DL-Lite}$ (wo sie vermuten, dass die Konflikt-Beschränkung aufgrund struktureller Eigenschaften Probleme vereinfachen könnte) und unter IAR-Semantik.

Das Paper schließt mit der Feststellung, dass die Kombination von Eigenschaften für praktische Anwendungen zwar wünschenswert ist (z. B. die Generierung von Erklärungen, die sowohl minimal als auch konflikt-beschränkt sind), dies jedoch nicht zwangsläufig mit den Kosten einer erhöhten rechnerischen Unbehandbarkeit für die gängigsten Kombinationen einhergeht.