【学术牢骚】一个我认为并不严格的证明

最近对图论里的一些东西比较着迷，读到了下面这篇论文：

Finding Paths with Minimum Shared Edges

这篇论文提出了一个叫Minimum Shared Edges的问题，并说明了该问题的决策版本是NP-Complete的。

如果你在阅读这篇博客，你不需要阅读这篇论文。关于这个Minimum Shared Edges问题，你只需要知道它要求给出一族路径作为答案即可。

我只想谈谈下面这段内容：

高光部分快速带过了对MSE的NP性的证明。但问题是，此处certificate的长度是什么级别的呢？

如果证书长度是超多项式的，比方说是级别的，那么这个证书就是不合法的。

论文中的证书是，是路径的集合。那么，我们就须要证明路径的数量是多项式级别的，才能说这个问题存在多项式时间的验证机。

我并没有看到这样子的说明。

那为什么我们在传统的那些NP完全问题里也看不到这样子的说明呢？这是因为它们证书大多是显然与输入同级别的。比方说VERTEX-COVER问题，证书就是符合需要的那些顶点，而顶点的数量显然的，其中是输入的长度。因此证书的长度不会超标。

然而，在与路径相关的问题里，输入通常是图。假设的顶点数是，那么输入的规模就是（因为边数可以达到级别）。而路径数可以达到指数级别。此时，我们就不能再忽略证书的长度带来的问题。

下面我给出一个示例。

考虑我在【科研点子】流量标注的可推断性与图兰问题 | Home of Mr. 5谈论的东西。我们考虑下面这个语言：

，其中为有点的无向图，为正整数，上存在到的条路径，这条路径组成的子图不包含不可标注边。

我们要问：吗？

答案是肯定的。我们仍然直接以答案路径集合作为证书，设的定点数为，一定不超过，即不超过边数，否则就一定会有路径没有自己独特的边，从而产生矛盾。因此证书的长度一定是合法的。

这是一个比较简单的例子。但我们还可以考虑下面这一类问题：

，其中为有点的无向图，为正整数，上存在到的条路径，这条路径组成的子图不包含。

这里的可能是各种东西，比方说等。此时，如果能够证明排除这种结构就会导致路径数低于指数级，那么就一定属于。

这里，我们看到了将极值图论与复杂性分析结合起来的可能。

另一个合理的猜想是，the opposite way是否是可能的呢？我们能否根据某个图论问题的复杂性（比方说属于NP），推出相关图结构的某些量化性质呢？这个猜想或许更加重要。

下面这篇最近的论文给出了一个结合Turan定理与算法复杂性的例子。

Turan’s Theorem Through Algorithmic Lens