Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Strong Backdoors for Default Logic

  • Conference paper
  • First Online:
Theory and Applications of Satisfiability Testing – SAT 2016 (SAT 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9710))

Abstract

In this paper, we introduce a notion of backdoors to Reiter’s propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, positive-unit). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in \({\mathrm {para}}\text {-}\varDelta ^P_2\), or in \({\mathrm {para}}\text {-}\mathrm {NP}\), depending on the target class.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Beyersdorff, O., Meier, A., Thomas, M., Vollmer, H.: The complexity of reasoning for fragments of default logic. J. Logic Comput. 22(3), 587–604 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  2. Boros, E., Crama, Y., Hammer, P.L.: Polynomial-time inference of all valid implications for horn and related formulae. Ann. Math. Artif. Intell. 1(1–4), 21–32 (1990)

    Article  MATH  Google Scholar 

  3. Boros, E., Hammer, P.L., Sun, X.: Recognition of q-Horn formulae in linear time. Discrete Appl. Math. 55(1), 1–13 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chen, J., Chor, B., Fellows, M.R., Huang, X., Juedes, D.W., Kanji, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216–231 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40–42), 3736–3756 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Volume Formal Models and Semantics, pp. 193–242. Elsevier Science Publishers, North-Holland (1990)

    Google Scholar 

  7. Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-order Logic: A Language Theoretic Approach. Cambridge University Press, Cambridge (2012)

    Book  MATH  Google Scholar 

  8. Creignou, N., Meier, A., Thomas, M., Vollmer, H.: The complexity of reasoning for fragments of autoepistemic logic. ACM Trans. Comput. Logic 13(2), 1–22 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. de Haan, R., Szeider, S.: Fixed-parameter tractable reductions to SAT. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 85–102. Springer, Heidelberg (2014)

    Google Scholar 

  10. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)

    Book  MATH  Google Scholar 

  11. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)

    Book  MATH  Google Scholar 

  12. Dvořák, W., Ordyniak, S., Szeider, S.: Augmenting tractable fragments of abstract argumentation. Artif. Intell. 186, 157–173 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Egly, U., Eiter, T., Tompits, H., Woltran, S.: Solving advanced reasoning tasks using quantified boolean formulas. In: Kautz, H., Porter, B. (eds.) Proceedings of the 17th Conference on Artificial Intelligence (AAAI 2000), Austin, TX, USA, pp. 417–422. The AAAI Press, July 2000

    Google Scholar 

  14. Fernau, H.: A top-down approach to search-trees: improved algorithmics for 3-hitting set. Algorithmica 57(1), 97–118 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fichte, J., Meier, A., Schindler, I.: Strong Backdoors for Default Logic. Technical report. CoRR: abs/1483200, arXiv (2016)

    Google Scholar 

  16. Fichte, J.K., Szeider, S.: Backdoors to normality for disjunctive logic programs. ACM Trans. Comput. Logic 17(1), 7 (2015)

    Article  MathSciNet  Google Scholar 

  17. Fichte, J.K., Szeider, S.: Backdoors to tractable answer-set programming. Artif. Intell. 220, 64–103 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Flum, J., Grohe, M.: Describing parameterized complexity classes. Inf. Comput. 187(2), 291–319 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  19. Flum, J., Grohe, M.: Parameterized Complexity Theory. Theoretical Computer Science, vol. 14. Springer, Heidelberg (2006)

    MATH  Google Scholar 

  20. Gaspers, S., Szeider, S.: Backdoors to satisfaction. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 287–317. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  21. Gottlob, G.: Complexity results for nonmonotonic logics. J. Logic Comput. 2(3), 397–425 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gottlob, G., Pichler, R., Wei, F.: Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artif. Intell. 174(1), 105–132 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  23. Gottlob, G., Scarcello, F., Sideri, M.: Fixed-parameter complexity in AI and nonmonotonic reasoning. Artif. Intell. 138(1–2), 55–86 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  24. Gottlob, G., Szeider, S.: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems. Comput. J. 51(3), 303–325 (2006). Survey paper

    Article  Google Scholar 

  25. Marek, V.W., Truszczyński, M.: Nonmonotonic Logic: Context-Dependent Reasoning. Artificial Intelligence. Springer, Heidelberg (1993)

    Book  MATH  Google Scholar 

  26. McCarthy, J.: Circumscription – a form of non-monotonic reasoning. Artif. Intell. 13, 27–39 (1980)

    Article  MATH  Google Scholar 

  27. McDermott, D., Doyle, J.: Non-montonic logic I. Artif. Intell. 13, 41–72 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  28. Meier, A., Schindler, I., Schmidt, J., Thomas, M., Vollmer, H.: On the parameterized complexity of non-monotonic logics. Arch. Math. Logic 54(5–6), 685–710 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  29. Moore, R.C.: Semantical considerations on modal logic. Artif. Intell. 25, 75–94 (1985)

    Article  MATH  Google Scholar 

  30. Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic CNF formulas. Theor. Comput. Sci. 481, 85–99 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  31. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)

    MATH  Google Scholar 

  32. Pfandler, A., Rümmele, S., Szeider, S.: Backdoors to abduction. In: Rossi, F. (ed.) Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China, pp. 1046–1052. The AAAI Press, August 2013

    Google Scholar 

  33. Reiter, R.: A logic for default reasoning. Artif. Intell. 13, 81–132 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  34. Rosati, R.: Model checking for nonmonotonic logics: algorithms and complexity. In: Dean, T. (ed.) Proceedings of the 16th International Joint Conference on Artificial Intelligence (ICJAI 1999), Stockholm, Sweden. The AAAI Press, July 1999

    Google Scholar 

  35. Samer, M., Szeider, S.: Fixed-parameter tractability. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, pp. 425–454. IOS Press, Amsterdam (2009)

    Google Scholar 

  36. Schaefer, T.J.: The complexity of satisfiability problems. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), San Diego, CA, USA, pp. 216–226. Association for Computing Machinery, New York (1978)

    Google Scholar 

  37. Schnorr, C.-P.: On self-transformable combinatorial problems. In: König, H., Korte, B., Ritter, K. (eds.) Mathematical Programming at Oberwolfach. Mathematical Programming Studies, vol. 14, pp. 225–243. Springer, Heidelberg (1981)

    Chapter  Google Scholar 

  38. Stillman, J.P.: It’s not my default: the complexity of membership problems in restricted propositional default logics. In: Dietterich, T., Swartout, W. (eds.) Proceedings of the 8th National Conference on Artificial Intelligence (AAAI 1990), Boston, MA, USA, vol. 1, pp. 571–578. The AAAI Press, July 1990

    Google Scholar 

  39. Stillman, J.P.: The complexity of horn theories with normal unary defaults. In: Proceedings of the 8th Canadian Artificial Intelligence Conference (AI 1990) (1990)

    Google Scholar 

  40. Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 188–202. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  41. Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico, pp. 1173–1178. Morgan Kaufmann, August 2003

    Google Scholar 

  42. Williams, R., Gomes, C., Selman, B.: On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In: Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT 2003), Portofino, Italy, pp. 222–230, May 2003

    Google Scholar 

Download references

Acknowledgements

The first author gratefully acknowledges support by the Austrian Science Fund (FWF), Grant Y698. He is also affiliated with the Institute of Computer Science and Computational Science at University of Potsdam, Germany. The second and third author gratefully acknowledge support by the German Research Foundation (DFG), Grant ME 4279/1-1. The authors thank Jonni Virtema for pointing out Lemma 6 and Sebastian Ordyniak for discussions on Lemma 11. The authors acknowledge the helpful comments of the anonymous reviewers.

Author information

Authors and Affiliations

  1. Technische Universität Wien, Wien, Austria

    Johannes K. Fichte

  2. Leibniz Universität Hannover, Hannover, Germany

    Arne Meier & Irina Schindler

Authors
  1. Johannes K. Fichte
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arne Meier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Irina Schindler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Johannes K. Fichte .

Editor information

Editors and Affiliations

  1. Aix-Marseille Université, Marseille, France

    Nadia Creignou

  2. Université d'Artois, Lens, France

    Daniel Le Berre

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Fichte, J.K., Meier, A., Schindler, I. (2016). Strong Backdoors for Default Logic. In: Creignou, N., Le Berre, D. (eds) Theory and Applications of Satisfiability Testing – SAT 2016. SAT 2016. Lecture Notes in Computer Science(), vol 9710. Springer, Cham. https://doi.org/10.1007/978-3-319-40970-2_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-40970-2_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-40969-6

  • Online ISBN: 978-3-319-40970-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation