 |
    |
Complex Analogies: Remarks on the Complexity of HDTP
Robert Robere1 and Tarek Richard Besold2
1University of Toronto, Canada
robere@cs.toronto.edu
2Institute of Cognitive Science, University of Osnabrück, Germany
tbesold@uos.de
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.
LNAI 7691, p. 530 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012