Strategic Argumentation is NP-Complete
Guido Governatori, Francesco Olivieri, Simone Scannapieco, Antonino Rotolo, Matteo Cristani · Frontiers in artificial intelligence and applications · 2014
We study the complexity of the Strategic Argumentation Problem for 2-player dialogue games where a player should decide what move (set of rules) to play at each turn in order to prove (disprove) a given thesis. We show that this is an NP-complete problem.