Complex Analogies: Remarks on the Complexity of HDTP

Robert Robere, Tarek Richard Besold

Abstract

After an introduction to Heuristic-Driven Theory Projection (HDTP) as framework for computational analogy-making, and a compact primer on parametrized complexity theory, we provide a complexity analysis of the key mechanisms underlying HDTP, together with a short discussion of and reflection on the obtained results. Amongst others, we show that restricted higher-order anti-unification as currently used in HDTP is W[1]-hard (and thus NP-hard) already for quite simple cases. Also, we obtain W[2]-hardness, and NP-completeness, for the original mechanism used for reducing second-order to first-order anti-unifications in the basic version of the HDTP system.
BibTeX
@inproceedings{robere2012complex,
  author = {Robert Robere and Tarek Richard Besold},
  title = {{Complex Analogies: Remarks on the Complexity of HDTP}},
  booktitle = {Australasian Conference on Artificial Intelligence},
  year = {2012},
  doi = {10.1007/978-3-642-35101-3\_45},
}

Loading related content...

Figure