论文部分内容阅读
Inductive learning is an important subject in artificial intelligence.As a concern of theoreticalcomputer science,this paper investigates the complexity of induction of structural descriptions which isfundamental to inductive learning.The general complexity is derived,and a way of approaching theinduction,namely,computing the maximal common generalizations by pairing,is also presented with itsinherent complexity.A group of NP-complete and NP-hard problems are introduced when showing the complexities.
Inductive learning is an important subject in artificial intelligence. As a concern of theoretical computer science, this paper investigates the complexity of induction of structural descriptions which isfundamental to inductive learning. The general complexity is derived, and a way of approaching the induction, namely, computing the maximal common generalizations by pairing, is also presented with its inherent complexity. A group of NP-complete and NP-hard problems are introduced when showing the complexities.