On the Complexity of Induction of Structural Descriptions

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 is fundamental 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.