We study the complexity of the Strategic Argumentation Problem for 2-player dialogue games where a player should decide what move to play at each turn in order to prove (disprove) a given claim. We shall prove that this is an NP-complete problem. The result covers one the most popular argumentation semantics proposed by Dung [4]: the grounded semantics.
Strategic argumentation under grounded semantics is NP-complete / Governatori, Guido; Maher, Michael J.; Olivieri, Francesco; Rotolo, Antonino; Scannapieco, Simone. - STAMPA. - 8953:(2015), pp. 379-387. (Intervento presentato al convegno 12th European Conference on Multi-Agent Systems, EUMAS 2014 tenutosi a Prague, Czech Republic nel 2014) [10.1007/978-3-319-17130-2_26].
Strategic argumentation under grounded semantics is NP-complete
ROTOLO, ANTONINO;
2015
Abstract
We study the complexity of the Strategic Argumentation Problem for 2-player dialogue games where a player should decide what move to play at each turn in order to prove (disprove) a given claim. We shall prove that this is an NP-complete problem. The result covers one the most popular argumentation semantics proposed by Dung [4]: the grounded semantics.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.