第三章学习的计算理论 示例学习的优化问题 1)最优覆盖问题(MCV)生成具有最少数目公式的覆盖; (2)最简公式问题( MCOMP)生成具有最少数目选择子及属 性值的公式,或极大复合; (3)最优示例学习问题(OPL)生成只由最简公式组成的最 优覆盖。 二.最优覆盖问题是NP难题 定理3.1:已知两个问题P1和P2,如果P1是NP难题。并且P1可 在多项式时间内归纳到P2,则P2也是NP难题,并称P1可 (多项式)归纳到P2,如果P2反过来也能归纳到P1,则称 P1和P2是等价的。 定理32:最优集合覆盖问题( SETCV是从一个有穷集合的有 穷覆盖中,找到一个具有最小基数的子覆盖。即设T是 个m个点的集合,F是T的子集族。F={S1…,S},其中 Sicko setcv是找到F的具有最少数目的子族F,第三章 学习的计算理论 一. 示例学习的优化问题 (1) 最优覆盖问题(MCV)—生成具有最少数目公式的覆盖； (2) 最简公式问题(MCOMP)—生成具有最少数目选择子及属 性值的公式，或极大复合； (3) 最优示例学习问题(OPL)—生成只由最简公式组成的最 优覆盖。 二. 最优覆盖问题是NP难题 定理3.1：已知两个问题P1和P2,如果P1是NP难题。并且P1可 在多项式时间内归纳到P2,则P2也是NP难题，并称P1可 （多项式）归纳到P2,如果P2反过来也能归纳到P1,则称 P1和P2是等价的。 定理3.2：最优集合覆盖问题(SETCV)是从一个有穷集合的有 穷覆盖中，找到一个具有最小基数的子覆盖。即设T是 一个m个点的集合，F是T的子集族。 F={S1 , …,Sp}, 其中 Si  T。SETCV是找到F的具有最少数目的子族F’, 