ML Anthology

Analogy Is NP-Hard

Shinji Furuya, Satoru Miyano
ALT 1991 pp. 207-212
/alt/1991/furuya1991alt-analogy/

Abstract

Analogy is described in predicate logic. This paper deals with the analogy without any function symbols except constants. We show that the problem of deciding whether a given atomic formula can be inferred by analogy is NP-hard even in such a simple case.

Semantic Scholar

Cite

Text

Furuya and Miyano. "Analogy Is NP-Hard." International Conference on Algorithmic Learning Theory, 1991.

Markdown

[Furuya and Miyano. "Analogy Is NP-Hard." International Conference on Algorithmic Learning Theory, 1991.](https://mlanthology.org/alt/1991/furuya1991alt-analogy/)

BibTeX

@inproceedings{furuya1991alt-analogy,
  title     = {{Analogy Is NP-Hard}},
  author    = {Furuya, Shinji and Miyano, Satoru},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1991},
  pages     = {207-212},
  url       = {https://mlanthology.org/alt/1991/furuya1991alt-analogy/}
}