Search Results

Documents authored by Cooper, Martin C.

Document
DOI: 10.4230/LIPIcs.CP.2022.9
Complexity of Minimum-Size Arc-Inconsistency Explanations

Authors: Christian Bessiere, Clément Carbonnel, Martin C. Cooper, and Emmanuel Hebrard

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Explaining the outcome of programs has become one of the main concerns in AI research. In constraint programming, a user may want the system to explain why a given variable assignment is not feasible or how it came to the conclusion that the problem does not have any solution. One solution to the latter is to return to the user a sequence of simple reasoning steps that lead to inconsistency. Arc consistency is a well-known form of reasoning that can be understood by a human. We consider explanations as sequences of propagation steps of a constraint on a variable (i.e. the ubiquitous revise function in arc consistency algorithms) that lead to inconsistency. We characterize, on binary CSPs, cases for which providing a shortest such explanation is easy: when domains are Boolean or when variables have maximum degree two. However, these polynomial cases are tight. Providing a shortest explanation is NP-hard if the maximum degree is three, even if the number of variables is bounded, or if domain size is bounded by three. It remains NP-hard on trees, despite the fact that arc consistency is a decision procedure on trees. Finally, the problem is not FPT-approximable unless the Gap-ETH is false.
Cite as

Christian Bessiere, Clément Carbonnel, Martin C. Cooper, and Emmanuel Hebrard. Complexity of Minimum-Size Arc-Inconsistency Explanations. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bessiere_et_al:LIPIcs.CP.2022.9,
  author =	{Bessiere, Christian and Carbonnel, Cl\'{e}ment and Cooper, Martin C. and Hebrard, Emmanuel},
  title =	{{Complexity of Minimum-Size Arc-Inconsistency Explanations}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.9},
  URN =		{urn:nbn:de:0030-drops-166380},
  doi =		{10.4230/LIPIcs.CP.2022.9},
  annote =	{Keywords: Constraint programming, constraint propagation, minimum explanations, complexity}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.13
Isomorphisms Between STRIPS Problems and Sub-Problems

Authors: Martin C. Cooper, Arnaud Lequen, and Frédéric Maris

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance P and a sub-instance of another instance P'. One application of such an isomorphism is to efficiently produce a compiled form containing all solutions to P from a compiled form containing all solutions to P'. In this paper, we study the complexity of both problems. We show that the former is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the latter to be NP-complete, we propose an algorithm to build an isomorphism, when possible. We report extensive experimental trials on benchmark problems which demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.
Cite as

Martin C. Cooper, Arnaud Lequen, and Frédéric Maris. Isomorphisms Between STRIPS Problems and Sub-Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.CP.2022.13,
  author =	{Cooper, Martin C. and Lequen, Arnaud and Maris, Fr\'{e}d\'{e}ric},
  title =	{{Isomorphisms Between STRIPS Problems and Sub-Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.13},
  URN =		{urn:nbn:de:0030-drops-166426},
  doi =		{10.4230/LIPIcs.CP.2022.13},
  annote =	{Keywords: planning, isomorphism, complexity, constraint propagation}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.21
On the Tractability of Explaining Decisions of Classifiers

Authors: Martin C. Cooper and João Marques-Silva

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Explaining decisions is at the heart of explainable AI. We investigate the computational complexity of providing a formally-correct and minimal explanation of a decision taken by a classifier. In the case of threshold (i.e. score-based) classifiers, we show that a complexity dichotomy follows from the complexity dichotomy for languages of cost functions. In particular, submodular classifiers allow tractable explanation of positive decisions, but not negative decisions (assuming P≠NP). This is an example of the possible asymmetry between the complexity of explaining positive and negative decisions of a particular classifier. Nevertheless, there are large families of classifiers for which explaining both positive and negative decisions is tractable, such as monotone or linear classifiers. We extend tractable cases to constrained classifiers (when there are constraints on the possible input vectors) and to the search for contrastive rather than abductive explanations. Indeed, we show that tractable classes coincide for abductive and contrastive explanations in the constrained or unconstrained settings.
Cite as

Martin C. Cooper and João Marques-Silva. On the Tractability of Explaining Decisions of Classifiers. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.CP.2021.21,
  author =	{Cooper, Martin C. and Marques-Silva, Jo\~{a}o},
  title =	{{On the Tractability of Explaining Decisions of Classifiers}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.21},
  URN =		{urn:nbn:de:0030-drops-153125},
  doi =		{10.4230/LIPIcs.CP.2021.21},
  annote =	{Keywords: machine learning, tractability, explanations, weighted constraint satisfaction}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2020.4
Graphical Models: Queries, Complexity, Algorithms (Tutorial)

Authors: Martin C. Cooper, Simon de Givry, and Thomas Schiex

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Graphical models (GMs) define a family of mathematical models aimed at the concise description of multivariate functions using decomposability. We restrict ourselves to functions of discrete variables but try to cover a variety of models that are not always considered as "Graphical Models", ranging from functions with Boolean variables and Boolean co-domain (used in automated reasoning) to functions over finite domain variables and integer or real co-domains (usual in machine learning and statistics). We use a simple algebraic semi-ring based framework for generality, define associated queries, relationships between graphical models, complexity results, and families of algorithms, with their associated guarantees.
Cite as

Martin C. Cooper, Simon de Givry, and Thomas Schiex. Graphical Models: Queries, Complexity, Algorithms (Tutorial). In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.STACS.2020.4,
  author =	{Cooper, Martin C. and de Givry, Simon and Schiex, Thomas},
  title =	{{Graphical Models: Queries, Complexity, Algorithms}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.4},
  URN =		{urn:nbn:de:0030-drops-118654},
  doi =		{10.4230/LIPIcs.STACS.2020.4},
  annote =	{Keywords: Computational complexity, tree decomposition, graphical models, submodularity, message passing, local consistency, artificial intelligence, valued constraints, optimization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.19
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns

Authors: Clément Carbonnel, David A. Cohen, Martin C. Cooper, and Stanislav Zivny

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.
Cite as

Clément Carbonnel, David A. Cohen, Martin C. Cooper, and Stanislav Zivny. On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{carbonnel_et_al:LIPIcs.STACS.2018.19,
  author =	{Carbonnel, Cl\'{e}ment and Cohen, David A. and Cooper, Martin C. and Zivny, Stanislav},
  title =	{{On Singleton Arc Consistency for CSPs Defined by Monotone Patterns}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.19},
  URN =		{urn:nbn:de:0030-drops-84876},
  doi =		{10.4230/LIPIcs.STACS.2018.19},
  annote =	{Keywords: constraint satisfaction problems, forbidden patterns, singleton arc consistency}
}
Document
DOI: 10.4230/DFU.Vol7.15301.113
Hybrid Tractable Classes of Constraint Problems

Authors: Martin C. Cooper and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
We present a survey of complexity results for hybrid constraint satisfaction problems (CSPs) and valued constraint satisfaction problems (VCSPs). These are classes of (V)CSPs defined by restrictions that are not exclusively language-based or structure-based.
Cite as

Martin C. Cooper and Stanislav Zivny. Hybrid Tractable Classes of Constraint Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 113-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{cooper_et_al:DFU.Vol7.15301.113,
  author =	{Cooper, Martin C. and Zivny, Stanislav},
  title =	{{Hybrid Tractable Classes of Constraint Problems}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{113--135},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.113},
  URN =		{urn:nbn:de:0030-drops-69616},
  doi =		{10.4230/DFU.Vol7.15301.113},
  annote =	{Keywords: Constraint satisfaction problems, Optimisation, Tractability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact