On the complexity of constraint-based theory extraction

Mario Boley, Thomas Gärtner

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

In this paper we rule out output polynomial listing algorithms for the general problem of discovering theories for a conjunction of monotone and anti-monotone constraints as well as for the particular subproblem in which all constraints are frequency-based. For the general problem we prove a concrete exponential lower time bound that holds for any correct algorithm and even in cases in which the size of the theory as well as the only previous bound are constant. For the case of frequency-based constraints our result holds unless P = NP. These findings motivate further research to identify tractable subproblems and justify approaches with exponential worst case complexity.

Original languageEnglish
Title of host publicationDiscovery Science - 12th International Conference, DS 2009, Proceedings
PublisherSpringer
Pages92-106
Number of pages15
ISBN (Print)3642047467, 9783642047466
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event12th International Conference on Discovery Science, DS 2009 - Porto, Portugal
Duration: 3 Oct 20095 Oct 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5808
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Discovery Science, DS 2009
Country/TerritoryPortugal
CityPorto
Period3/10/095/10/09

Cite this