pith. sign in

arxiv: 1201.0478 · v1 · pith:DBTFSSB7new · submitted 2012-01-02 · 💻 cs.AI · cs.CC

Technical Note: Exploring Sigma^P₂ / Pi^P₂-hardness for Argumentation Problems with fixed distance to tractable classes

classification 💻 cs.AI cs.CC
keywords classesreasoningargumentationcomplexitydistancefixedgraphproblems
0
0 comments X
read the original abstract

We study the complexity of reasoning in abstracts argumentation frameworks close to graph classes that allow for efficient reasoning methods, i.e.\ to one of the classes of acyclic, noeven, biparite and symmetric AFs. In this work we show that certain reasoning problems on the second level of the polynomial hierarchy still maintain their full complexity when restricted to instances of fixed distance to one of the above graph classes.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.