Kazuhisa Makino Visited the School of Data Analysis and Artificial Intelligence

On May 14 Kazuhisa Makino, Associate Professor at the Research Institute for Mathematical Sciences at Kyoto University spoke on ‘Computational Aspects of Monotone Dualization’ at the colloquium of the Faculty of Computer Science.

Abstract
Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including computer science, artificial intelligence, data mining, machine learning, and game theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 30 years. We briefly survey computational results for this problem, which includes the remarkable result by M.L. Fredman and L.G. Khachiyan that the problem is solvable in quasi-polynomial time (and thus most likely not coNP-hard), as well as on follow-up works.

 Dualization of a Monotone Boolean Function (PDF, 1010 Кб)

On May 18 Kazuhisa Makino presented the report ‘On Computing all Abductive Explanations from a Propositional Horn Theory’ during the seminar of the International Laboratory for Intelligent Systems and Structural Analysis.

Abstract
Abduction is a fundamental mode of reasoning with applications in many areas of AI and Computer Science. The computation of abductive explanations is an important computational problem, which is at the core of early systems such as the ATMS and Clause Management Systems and is intimately related to prime implicate generation in propositional logic. Many algorithms have been devised for computing some abductive explanation, and the complexity of the problem has been well studied. However, little attention has been paid to the problem of computing multiple explanations, and in particular all explanations for an abductive query. We fill this gap and consider the computation of all explanations of an abductive query from a propositional Horn theory, or of a polynomial subset of them. Our study pays particular attention to the form of the query, ranging from a literal to a compound formula, to whether explanations are based on a set of abducible literals and to the representation of the Horn theory, either by a Horn conjunctive normal form (CNF) or model-based in terms of its characteristic models. For these combinations, we present either tractability results in terms of polynomial total-time algorithms, intractability results in terms of nonexistence of such algorithms (unless P = NP), or semi-tractability results in terms of solvability in quasi-polynomial time, established by polynomial-time equivalence to the problem of dualizing a monotone CNF expression. Our results complement previous results in the literature, and refute a longstanding conjecture by Selman and Levesque. They elucidate the complexity of generating all abductive explanations and shed light on related problems such as generating sets of restricted prime implicates of a Horn theory. The algorithms for tractable cases can be readily applied for generating a polynomial subset of explanations in polynomial time.