Resumo Técnico: Combinação de Propriedades para Abdução de ABox sob Semântica de Reparo para $\mathcal{EL}^\bot$

Declaração do Problema

O artigo aborda o problema da abdução de ABox dentro de Lógicas de Descrição (especificamente $\mathcal{EL}^\bot$) sob semântica de reparo. A abdução busca encontrar uma hipótese (um conjunto de asserções $\mathcal{H}$) que, ao ser adicionada a uma base de conhecimento inconsistente $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$, torne verdadeira uma implicação ausente (observação) $\alpha$.

No contexto da semântica de reparo, as inconsistências são tratadas considerando "reparos" (subconjuntos consistentes maximais da ABox). O artigo foca em duas semânticas específicas:

1. Semântica Brave (Corajosa): $\alpha$ é implicado se for verdadeiro em pelo menos um reparo.
2. Semântica AR (Todos os Reparos): $\alpha$ é implicado se for verdadeiro em todos os reparos.

Enquanto trabalhos anteriores [17] investigaram a complexidade computacional da abdução para propriedades desejáveis individuais (por exemplo, não-trivialidade, restrição de assinatura, confinamento de conflito e vários critérios de minimalidade), este artigo investiga as combinações dessas propriedades. A questão central de pesquisa é se exigir que uma hipótese satisfaça múltiplas propriedades simultaneamente (por exemplo, ser tanto não-trivial quanto confinadora de conflitos, ou subconjunto-minimal e com restrição de assinatura) leva a um aumento na complexidade computacional em comparação com a satisfação delas isoladamente.

Metodologia

Os autores analisam a complexidade computacional de dois problemas de raciocínio fundamentais para combinações de propriedades:

1. Problema de Existência: Existe uma hipótese que satisfaça as propriedades dadas?
2. Problema de Verificação: Uma determinada ABox $\mathcal{H}$ satisfaz as propriedades e constitui uma hipótese válida?

O estudo abrange combinações de:

• Propriedades Básicas:
  • Não-trivialidade: A hipótese não contém a observação $\alpha$.
  • Restrição de Assinatura ($\Sigma$-restrita): A hipótese utiliza apenas símbolos de uma assinatura especificada.
  • Confinamento de Conflito: A hipótese não introduz novos conflitos além daqueles já presentes em $\mathcal{K}$.
• Critérios de Minimalidade:
  • Subconjunto-minimalidade ($\subseteq$-minimal): Nenhum subconjunto próprio da hipótese é uma hipótese válida.
  • Minimalidade de Cardinalidade ($\leq$-minimal): Nenhum hipótese com menos asserções é válida.
  • Minimalidade de Conflito ($\subseteq_c$-minimal): Nenhum hipótese introduz um conjunto estritamente menor de conflitos.

A análise baseia-se em classes de complexidade padrão ($\text{P}, \text{NP}, \text{coNP}, \text{DP}, \Sigma^P_2, \Pi^P_2$) e emprega reduções de problemas conhecidos (por exemplo, validade de QBF, combinação de implicação/não-implicação) para estabelecer limites inferiores, e algoritmos de "adivinhar e verificar" (guess-and-check) com chamadas de oráculo para estabelecer limites superiores.

Principais Contribuições e Resultados

1. Combinações de Propriedades Básicas (Não-Minimalidade)

O artigo demonstra que combinar propriedades básicas geralmente não aumenta a complexidade além da maior complexidade das propriedades individuais.

• $\Sigma$-restrição + Não-trivialidade: A complexidade permanece $\text{NP}$-completa para semântica Brave e $\Sigma^P_2$-completa para semântica AR.
• Confinamento de Conflito + Não-trivialidade / $\Sigma$-restrição: A complexidade aumenta para $\Sigma^P_2$-completa para ambas as semânticas Brave e AR. Este é um resultado notável porque hipóteses confinadoras de conflito sozinhas são $\Sigma^P_2$-completas para Brave, mas apenas $\text{coNP}$-completas para AR; adicionar não-trivialidade ou restrição de assinatura eleva a complexidade de AR para igualar o caso Brave.

2. Combinações com Subconjunto-Minimalidade ($\subseteq$-minimalidade)

• Subconjunto-minimal + Não-trivial / $\Sigma$-restrito: A complexidade coincide com a de verificar hipóteses de subconjunto-minimal sozinho ($\text{DP}$-completo para Brave, $\Pi^P_2$-completo para AR).
• Subconjunto-minimal + Confinamento de Conflito:
  • Para a semântica Brave: $\text{DP}$-completo.
  • Para a semântica AR: A complexidade está em $\Pi^P_2$ e é $\text{coNP}$-difícil, mas o limite superior preciso permanece aberto.

3. Combinações com Minimalidade de Cardinalidade ($\leq$-minimalidade)

Ao contrário da subconjeto-minimalidade, a minimalidade de cardinalidade frequentemente leva ao aumento da complexidade quando combinada com outras propriedades, principalmente porque a hipótese trivial (tamanho 1) é frequentemente proibida por não-trivialidade ou restrições de assinatura.

• $\leq$-minimal + Não-trivial / $\Sigma$-restrito: A complexidade aumenta para $\text{DP}$-completo para Brave e $\Pi^P_2$-completo para AR.
• $\leq$-minimal + Confinamento de Conflito:
  • Para a semântica Brave: $\Pi^P_2$-completo.
  • Para a semântica AR: $\text{coNP}$-completo (permanece inalterado em relação ao caso de propriedade única devido ao Lema 6, que afirma que, para AR, a existência implica que a hipótese trivial é confinadora de conflito).

4. Combinações com Minimalidade de Conflito ($\subseteq_c$-minimalidade)

• $\subseteq_c$-minimal + Não-trivial / $\Sigma$-restrito: A complexidade é $\Pi^P_2$-completa para ambas as semânticas Brave e AR.
• O artigo observa que estender estes resultados para a minimalidade de cardinalidade de conflito ($\leq_c$) é difícil devido ao potencial de uma hipótese pequena disparar exponencialmente muitos novos conflitos, sugerindo uma possível dureza $\#\text{P}$.

Significância e Alegações

A principal observação do artigo é que exigir propriedades adicionais para as hipóteses frequentemente não leva a um aumento de complexidade, desde que as propriedades não sejam critérios de minimalidade envolvendo contagens de cardinalidade ou de conflitos.

• Principal Achado: Para a maioria das combinações de propriedades básicas (não-trivialidade, restrição de assinatura, confinamento de conflito) e subconjeto-minimalidade, a complexidade é governada pela "maior" complexidade entre as propriedades individuais envolvidas.
• Exceção: Combinações envolvendo minimalidade de cardinalidade ou minimalidade de conflito frequentemente resultam em classes de complexidade mais altas (por exemplo, movendo-se de $\text{coNP}$ para $\Pi^P_2$ ou $\text{DP}$).
• Escopo: Os resultados são específicos para $\mathcal{EL}^\bot$ sob as semânticas Brave e AR. Os autores observam que para lógicas mais expressivas (como $\mathcal{ALC}$), a complexidade é provavelmente dominada pelo próprio problema de implicação (ExpTime), tornando estas distinções de abdução menos impactantes.
• Trabalhos Futuros: Os autores identificam lacunas abertas, especificamente a complexidade precisa para hipóteses de AR de conflito $\subseteq$-minimal e o panorama de complexidade para combinações em $\text{DL-Lite}$ (onde suspeitam que o confinamento de conflito simplifique os problemas devido a propriedades estruturais) e sob semântica IAR.

O artigo conclui que, embora combinar propriedades seja desejável para aplicações práticas (por exemplo, gerar explicações que sejam simultaneamente mínimas e confinadoras de conflitos), essa desejabilidade não necessariamente traz o custo de uma maior intratabilidade computacional para as combinações mais comuns.