Resumo Técnico: Diversidade de Extensões em Argumentação Abstrata

Definição do Problema

A argumentação abstrata modela o raciocínio por meio de Estruturas de Argumentação (EAs), representadas como grafos direcionados onde os nós são argumentos e as arestas representam ataques. A semântica de uma EA define "extensões"—conjuntos de argumentos que satisfazem condições específicas de coerência (por exemplo, ausência de conflitos, admissibilidade, estabilidade). Embora as tarefas de raciocínio padrão determinem a existência de extensões ou o status de aceitação de argumentos individuais (crente ou cético), elas frequentemente falham em quantificar a distância estrutural entre essas extensões. Em cenários envolvendo negociação ou tomada de decisão, compreender se pontos de vista alternativos (extensões) são marginalmente diferentes ou fundamentalmente incompatíveis é crucial. Conceitos existentes, como a seleção de pontos de vista representativos ou a contagem de extensões, não medem explicitamente a "diversidade" ou dissimilaridade entre extensões inteiras.

Este artigo aborda essa lacuna introduzindo uma noção quantitativa de diversidade de extensões baseada na diferença simétrica ($A \triangle B = (A \cup B) \setminus (A \cap B)$). O problema central é determinar se uma EA admite duas extensões que diferem exatamente por $k$ argumentos, por pelo menos $k$ argumentos ou por no máximo $k$ argumentos, e calcular a diversidade máxima possível ($k_{max}$) para uma estrutura dada.

Metodologia

Os autores abordam o problema através de três pilares principais: definição formal, análise de complexidade computacional e avaliação experimental.

1. Definições Formais

A diversidade entre duas extensões $S$ e $T$ é definida como $d(S, T) = |S \triangle T|$. O artigo define vários problemas de decisão e otimização:

• $k$-Div-Arg$_\sigma$: Dados os argumentos $a, b$, existem duas extensões $\sigma$, $S$ e $T$, tais que $a \in S$, $b \in T$ e $d(S, T) = k$?
• $k$-Div-Ext$_\sigma$: A EA admite duas extensões $\sigma$ com distância $k$?
• Variantes: Os problemas também são definidos para diversidade $\ge k$ e $\le k$, bem como problemas de otimização para encontrar o máximo $k$ ($max$-$k$-Div).

2. Análise de Complexidade

O artigo fornece uma classificação sistemática da complexidade computacional para esses problemas através de várias semânticas:

• Semânticas sem Conflitos e Ingênua: Os problemas são geralmente NP-completos. Notavelmente, embora o raciocínio padrão (por exemplo, existência de extensão) seja polinomial para a semântica sem conflitos, determinar a diversidade é NP-difícil.
• Semânticas Admissível, Completa e Estável: A complexidade alinha-se com a aceitação crente, permanecendo NP-completa.
• Semânticas Semiestável, de Estágio e Preferida: Essas semânticas de nível superior aumentam a complexidade para $\Sigma_2^P$-completa para problemas de decisão envolvendo argumentos e extensões específicos.
• Diversidade Máxima: Determinar o limiar exato de diversidade máxima mostra-se DP-completo para semânticas de nível inferior e DP$_2$-completo para as semânticas semiestável e de estágio. Isso envolve verificar tanto a existência de uma solução com diversidade $k$ quanto a não existência de soluções com diversidade $> k$.

Os autores utilizam reduções a partir de problemas de complexidade padrão (3SAT, Conjunto Dominante, SAT-UNSAT e Fórmulas Booleanas Quantificadas) para estabelecer esses resultados de dureza.

3. Avaliação Experimental

Uma implementação protótipo foi desenvolvida usando Programação Lógica de Resposta a Conjuntos (ASP) e o solucionador ASPARTIX. O sistema calcula valores de diversidade mínima e máxima para EAs. Experimentos foram conduzidos em 270 instâncias do conjunto de benchmarks ICCMA 2025 (restrito a estruturas com $\le 1000$ argumentos) sob as semânticas admissível, completa e estável.

Contribuições Principais

1. Introdução da Diversidade por Diferença Simétrica: O artigo formaliza uma nova métrica para argumentação abstrata que quantifica o desacordo entre pontos de vista alternativos (extensões) em vez de apenas sua existência.
2. Paisagem Abrangente de Complexidade: Os autores fornecem uma classificação detalhada da complexidade do raciocínio sobre diversidade. Eles demonstram que, para certas semânticas (sem conflitos, ingênua), o raciocínio sobre diversidade é estritamente mais difícil do que o raciocínio padrão de aceitação, enquanto para outras, ele iguala a complexidade da aceitação crente.
3. Protótipo e Avaliação: O artigo apresenta uma implementação funcional e resultados empíricos iniciais, mostrando que o cálculo dos níveis de diversidade é viável para estruturas de tamanho médio, embora o tempo de execução varie significativamente dependendo da semântica e do alvo de diversidade específico (mínimo vs. máximo).

Resultados

• Complexidade: O estudo revela que o raciocínio sobre diversidade não é uniformemente fácil. Para a semântica sem conflitos, é NP-completo, contrastando com a solvabilidade em tempo polinomial da existência padrão de extensões. Para as semânticas semiestável e de estágio, o problema salta para o segundo nível da hierarquia polinomial ($\Sigma_2^P$).
• Descobertas Experimentais: Os experimentos indicam que os valores de diversidade variam substancialmente entre as instâncias. Embora muitas estruturas tenham extensões estruturalmente próximas (baixa diversidade), um subconjunto admite extensões fundamentalmente diferentes (alta diversidade). Os tempos de execução médios para calcular a diversidade máxima foram geralmente inferiores a 2 segundos para as instâncias testadas, sugerindo viabilidade prática para problemas de escala média.
• Não-Monotonicidade: Os autores observam que a diversidade não é nem monotônica nem antimonotônica, o que significa que adicionar argumentos a uma estrutura não aumenta ou diminui previsivelmente a diversidade máxima.

Significado e Afirmações

O artigo afirma que sua contribuição principal é tornar explícito quão fortemente pontos de vista alternativos e internamente coerentes em uma EA divergem. Ao ir além da simples aceitação ou contagem, essa medida quantitativa permite uma análise mais granular de situações argumentativas.

Os autores posicionam este trabalho como uma ferramenta para:

• Negociação e Tomada de Decisão: Identificar se os desacordos são superficiais (baixa diversidade) ou fundamentais (alta diversidade).
• Análise de Robustez: Alta diversidade implica baixa robustez das conclusões, pois a estrutura suporta posições radicalmente diferentes.
• Direções Futuras: Os autores sugerem modestamente que essa noção poderia ser estendida para argumentação baseada em lógica e aplicada à resposta de consultas consistentes em bases de conhecimento, mas não afirmam que essas aplicações são atualmente realizadas. Eles também identificam casos de complexidade abertos (por exemplo, diversidade mínima) e o potencial para abordagens de complexidade parametrizada como trabalho futuro.

O artigo conclui que, embora o custo computacional possa ser alto para certas semânticas, a capacidade de quantificar a "distância" entre pontos de vista oferece uma nova dimensão valiosa para analisar estruturas de argumentação abstrata.