3
* 1 ** 1 1
4
1 1 ** * *
5
1 * 1* * 1
6
* * *1 * 1
7
1 * 1* 1 *
定理3.4 最简公式问题是NP难题。 定理3.5 最优示例学习问题是NP难题。
归纳
SETCV
Pi
e
P0+ Pi i 1
三. 最小属性子集问题 定理3.6 最小属性子集问题(MAS)是NP难题。
使得F’是T的一个覆盖：F’ F,
|F|=最小；其中符号| |表示基数。
S S T 并且
SF'
SF
定理3.3 最优覆盖问题(MCV)是NP难题。
设 T={1, …,7} , F={S1, …,S6}
S1={1,4,5,7}, S2={3,4}, S3={2,5,7},S4={1,2,6}, S5={1,3,7},
学习的计算理论
一. 示例学习的优化问题
(1) 最优覆盖问题(MCV)—生成具有最少数目公式的覆盖； (2) 最简公式问题(MCOMP)—生成具有最少数目选择子及属
性值的公式，或极大复合；
(3) 最优示例学习问题(OPL)—生成只由最简公式组成的最 优覆盖。
二. 最优覆盖问题是NP难题 定理3.1：已知两个问题P1和P2,如果P1是NP难题。并且P1可
(4) 删去EM(PE|NE)所有在第j列含有非死元素的行；
(5) 如果EM(PE|NE)= ,则终止，并返回A;否则i←I+1. 并转向(3);
参考文献：
归纳学习—算法，理论，应用。 洪加荣著 P.46-52, P.57-58.
Point# S1 S2 S3 S4 S5 S6
1
