An encoding of argumentation problems using quadratic unconstrained binary optimization
This work addresses computational complexity in argumentation for AI and logic, but it is incremental as it applies existing QUBO encoding methods to a new domain.
The paper tackled the problem of encoding NP-Complete abstract argumentation problems into Quadratic Unconstrained Binary Optimization (QUBO) formulations to enable solutions using quantum and digital annealers, achieving correctness and applicability in tests with simulated annealing and a D-Wave quantum annealer.
In this paper, we develop a way to encode several NP-Complete problems in Abstract Argumentation to Quadratic Unconstrained Binary Optimization (QUBO) problems. In this form, a solution for a QUBO problem involves minimizing a quadratic function over binary variables (0/1), where the coefficients can be represented by a symmetric square matrix (or an equivalent upper triangular version). With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. A more conventional approach consists of developing approximate solvers, which, in this case, are used to tackle the intrinsic complexity. We performed tests to prove the correctness and applicability of classical problems in Argumentation and enforcement of argument sets. We compared our approach to two other approximate solvers in the literature during tests. In the final experimentation, we used a Simulated Annealing algorithm on a local machine. Also, we tested a Quantum Annealer from the D-Wave Ocean SDK and the Leap Quantum Cloud Service.