平面图闭邻域教学只需2个例子：旧上界是5，而区分1与2仍是NP难

平面图中所有闭邻域组成的教学问题，其无串通教学维度被压到2，只允许正例时压到4，两个界都取到过。 此前同一族上的已知上界是5和7，且平面图闭邻域是否满足教学维度不超过VC维的猜想一直未定。 对任意平面图给出不超过2的构造，并用一个平面图实例说明该界不能再小；正例情形同样给出不超过4的构造与取到4的实例。

构造按顶点度数分情况处理，把每个概念的示教集限制在很小的规模，再逐步修补冲突对。 做法是先给每个顶点一个初步示教集，再针对孪生顶点、饱和顶点和剩余顶点分四步修改，同时保持已区分的概念对不被破坏。 正例情形先在外平面图上得到不超过2的界，再借助外平面子图把平面图上的示教集扩到不超过4；一般情形用至多五个概念的类可单例教学，以及最小度至少5的平面图中存在度5顶点使该邻域族可单例教学。

判定无串通教学维度是否至多为1，在平面图闭邻域上仍是NP完全的，正例变体同样如此。 即使已知该族的上界是2，区分取值1和2依然困难。 从Planar-SAT归约，构造的平面图与闭邻域族规模为多项式，且归约同时覆盖一般与正例两种设定。

结果适用于平面图中闭邻域组成的概念类，覆盖一般与仅用正例两种无串通教学设定，上界分别为2和4且都紧。判定维度是否至多为1的NP完全性同样限定在这一族上。作者提出的下一步是把结论推广到具有线性邻域复杂度的图类，并考察无串通教学与样本压缩之间是否存在类似关系。

一般有限概念类上教学维度是否总不超过VC维仍未解决，本文只确认了平面图闭邻域这一族。作者也指出，把结果推广到线性邻域复杂度图类以及建立无串通教学与样本压缩的联系，都还是待做的方向。