Abstract: The essential issue in inductive logic programming is how to construct inductive hypotheses with optimal predicates selected from background knowledge and constrains satisfied.According to Occam’s principle,the simplest inductive hypotheses are the best.The computational complexity of constructing simplest inductive hypotheses,however,has not been fully investigated.Based on extension matrix,the main optimal problems in ILP are proven to be NP hard.A heuristic algorithm is then presented to solve the problems.The experiments show that the algorithm has superiority in the structures of inductive hypotheses produced.