Complexity of minimum-size arc-inconsistency explanations
Tóm tắt
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 several cases for which providing a shortest such explanation is easy: For instance when constraints are binary and variables have maximum degree two. However, these polynomial cases are tight. For instance, providing a shortest explanation is NP-hard when constraints are binary and the maximum degree is three, even if the number of variables is bounded. It remains NP-hard on trees, despite the fact that arc consistency is a decision procedure on trees. The problem is not even FPT-approximable unless the FPT
$$\ne $$
W[2] hypothesis is false.
Tài liệu tham khảo
Amilhastre, J., Fargier, H., & Marquis, P. (2002). Consistency restoration and explanations in dynamic CSPs application to configuration. Artificial Intelligence, 135(1–2), 199–234.
Bogaerts, B., Gamba, E., & Guns, T. (2021). A framework for step-wise explaining how to solve constraint satisfaction problems. Artificial Intelligence, 300, 103550.
Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., & Trevisan, L. (2017). From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In C. Umans (Ed.), Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17) (pp. 743–754). IEEE Computer Society
Chen, Y., Grohe, M., & Grüber, M. (2006). On parameterized approximability. Lecture Notes in Computer ScienceIn H. L. Bodlaender & M. A. Langston (Eds.), Parameterized and Exact Computation, Second International Workshop, IWPEC (Vol. 4169, pp. 109–120). Springer.
Cooper, M. C., de Givry, S., Sánchez-Fibla, M., Schiex, T., & Zytnicki, M. (2008). Virtual arc consistency for weighted CSP. In D. Fox & C. P. Gomes (Eds.), AAAI 2008 (pp. 253–258). AAAI Press.
Dinur, I. (2016). Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity, 128
Downey, R. G., & Fellows, M. R. (2012). Parameterized complexity. Springer Science & Business Media
Flum, J., & Grohe, M. (2006). Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman (Ed.), (1st ed.)
Gelder, A. V. (2008). Verifying RUP proofs of propositional unsatisfiability. In ISAIM
Goldberg, E., & Novikov, Y. (2003). Verification of proofs of unsatisfiability for CNF formulas. In 2003 Design, Automation and Test in Europe Conference and Exhibition (pp. 886–891)
Ignatiev, A., Narodytska, N., & Marques-Silva, J. (2019). Abduction-based explanations for machine learning models. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1511–1519.
Junker, U. (2004). QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In D. L. McGuinness & G. Ferguson (Eds), Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence (pp. 167–172). AAAI Press / The MIT Press
Junker, U. (2006). Configuration. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence (pp. 837–873). Elsevier.
Karp, R. (1972). Reducibility among combinatorial problems. In R. Miller & J. Thatcher (Eds.), Complexity of Computer Computations (pp. 85–103). Plenum Press.
Manurangsi, P., & Raghavendra, P. (2017). A birthday repetition theorem and complexity of approximating dense CSPs. In I. Chatzigiannakis, P. Indyk, F. Kuhn, & A. Muscholl (Eds), Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP’17), volume 80 of LIPIcs (pp. 78:1–78:15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Marx, D. (2010). Completely inapproximable monotone and antimonotone parameterized problems. In Proceedings of the 25th IEEE Annual Conference on Computational Complexity (pp. 181–187)
Shih, A., Choi, A., & Darwiche, A. (2018). A symbolic approach to explaining Bayesian network classifiers. In IJCAI’18 5103–5111. AAAI Press
Smith, B. M. (1992). How to solve the zebra problem, or path consistency the easy way. ECAI’92 (pp. 36–37). John Wiley and Sons
Sqalli, M. H., & Freuder, E. C. (1996). Inference-based constraint satisfaction supports explanation. In W. J. Clancey & D. S. Weld (Eds.), AAAI 96, IAAI 96 (Vol. 1, pp. 318–325). AAAI Press / The MIT Press.