1,721,026 research outputs found
More complexity results about reasoning over (m)CP-nets
Full text linkThis is the author accepted manuscript. The final version is available from IFAAMAS via the links in this recordAggregating preferences over combinatorial domains has several
applications in artificial intelligence. Due to the exponential nature
of combinatorial preferences, compact representations are
needed, and (m)CP-nets are among the most studied formalisms.
Unlike CP-nets, which received an extensive complexity analysis,
mCP-nets, as mentioned several times in the literature, lacked
such a thorough characterization. An initial complexity analysis for
mCP-nets was carried out only recently. In this paper, we further
investigate the complexity of mCP-nets. In particular, we prove
the Σ
P
3
-completeness of checking the existence of max optimal outcomes,
which was left as an open problem. We furthermore prove
that various tasks known to be feasible in polynomial time are
actually P-complete. This shows that these problems are inherently
sequential, and hence they cannot benefit from highly parallel computation.
The P-completeness results here proven are among the
very first of this kind in the computational social choice literature.This work was partly supported by the EPSRC grant EP/M025268/
“VADA: Value Added Data Systems – Principles and Architecture
Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting
No full textAggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed to represent them, and (m)CP-nets are among the most studied ones. Sequential and global voting are two different ways of aggregating preferences represented via CP-nets. In sequential voting, agents' preferences are aggregated feature-by-feature. For this reason, sequential voting may exhibit voting paradoxes, i.e., the possibility to select sub-optimal outcomes when preferences have specific feature dependencies. To avoid paradoxes in sequential voting, one has often assumed the (quite) restrictive constraint of O-legality, which imposes a shared common topological order among all the agents' CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during the preference aggregation process. For this reason, global voting is immune from the voting paradoxes of sequential voting, and hence there is no need to impose restrictions over the CP-nets' structure when preferences are aggregated via global voting. Sequential voting over O-legal CP-nets received much attention, and O-legality of CP-nets has often been required in other studies. On the other hand, global voting over non-O-legal CP-nets has not carefully been analyzed, despite it was explicitly stated in the literature that a theoretical comparison between global and sequential voting was highly promising and a precise complexity analysis for global voting has been asked for multiple times. In quite a few works, only very partial results on the complexity of global voting over CP-nets have been given. In this paper, we start to fill this gap by carrying out a thorough computational complexity analysis of global voting tasks, for Pareto and majority voting, over not necessarily O-legal acyclic binary polynomially connected (m)CP-nets. We show that all these problems belong to various levels of the polynomial hierarchy, and some of them are even in P or LOGSPACE. Our results are a notable achievement, given that the previously known upper bound for most of these problems was the complexity class EXPTIME. We provide various exact complexity results showing tight lower bounds and matching upper bounds for problems that (up to now) did not have any explicit non-obvious lower bound
A novel characterization of the complexity class Θ^P_k based on counting and comparison
No full textThe complexity class Θ^P_2, which is the class of languages recognizable by deterministic Turing machines in polynomial time with at most logarithmic many calls to an NP oracle, received extensive attention in the literature. Its complete problems can be characterized by different specific tasks, such as deciding whether the optimum solution of an NP problem is unique, or whether it is in some sense “odd” (e.g., whether its size is an odd number). In this paper, we introduce a new characterization of this class and its generalization Θ^P_k to the k-th level of the polynomial hierarchy. We show that problems in Θ^P_k are also those whose solution involves deciding, for two given sets A and B of instances of two Σ^P_{k−1}-complete (or Π^P_{k−1}-complete) problems, whether the number of “yes”-instances in A is greater than those in B. Moreover, based on this new characterization, we provide a novel sufficient condition for Θ^P_k-hardness. We also define the general problem Comp-Valid_k, which is proven here Θ^P_{k+1}-complete. Comp-Valid_k is the problem of deciding, given two sets A and B of quantified Boolean formulas with at most k alternating quantifiers, whether the number of valid formulas in A is greater than those in B. Notably, the problem Comp-Sat of deciding whether a set contains more satisfiable Boolean formulas than another set, which is a particular case of Comp-Valid_1, demonstrates itself as a very intuitive Θ^P_2-complete problem. Nonetheless, to our knowledge, it eluded its formal definition to date. In fact, given its strict adherence to the count-and-compare semantics here introduced, Comp-Valid_k is among the most suitable tools to prove Θ^P_k-hardness of problems involving the counting and comparison of the number of “yes”-instances in two sets. We support this by showing that the Θ^P_2-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ^P_k introduced in this paper
Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
No full textThe hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs G and H, decide whether H consists precisely of all minimal transversals of G (in which case we say that G is the dual of H). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in GC(log^2 n, PTIME), where GC(f(n), C) denotes the complexity class of all problems that after a nondeterministic guess of O(f(n)) bits can be decided (checked) within complexity class C. It was conjectured that non-DUAL is in GC(log^2 n, LOGSPACE). In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class GC(log^2 n, TC^0) which is a subclass of GC(log^2 n, LOGSPACE). We here refer to the logtime-uniform version of TC^0, which corresponds to FO(COUNT), i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for non-DUAL that requires to guess O(log^2 n) bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in FO(COUNT). From this result, by the well known inclusion TC^0 ⊆ LOGSPACE, it follows that DUAL belongs also to DSPACE[log^2 n]. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs G and H, computes in quadratic logspace a transversal of G missing in H
Explanations for Inconsistency-Tolerant Query Answering under Existential Rules
No full textQuerying inconsistent knowledge bases is a problem that has attracted a great deal of interest over the last decades. While several semantics of query answering have been proposed, and their complexity is rather well-understood, little attention has been paid to the problem of explaining query answers. Explainability has recently become a prominent problem in different areas of AI. In particular, explaining query answers allows users to understand not only what is entailed by an inconsistent knowledge base, but also why. In this paper, we address the problem of explaining query answers for existential rules under three popular inconsistency-tolerant semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs semantics. We provide a thorough complexity analysis for a wide range of existential rule languages and for different complexity measures
- …
