Complex Analogies: Remarks on the Complexity of HDTP
Lists
Only you see this
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...