检查$ n $顶点上的Digraph是否完全包含$ 10 sqrt {n} $在NL中强烈连接的组件

Question

我现在正在学习复杂性课程的测试。当我解决了先前的考试时，我看到了以下问题：证明$ n $顶点上所有有导图的语言$ l $，这些$ n $顶点完全包含$ 10 sqrt {n} $强烈连接的组件都在$ nl $中。

我们在课堂上看到，检查有指示的图是否完全包含$ c $紧密连接的组件在任何固定的$ c $中都在$ nl $中，但是我整天都考虑了这个问题，我绝对不知道该怎么做$ nl $当时所需的SCC数为$ 10 sqrt {n} $。在测试中，这个问题价值20分，所以不应该太难了，所以我认为也许我缺少一些重要的东西。

Answer 1

提示：假设$ c_1， ldots，c_ ell $是连接的组件，$ v_i $是$ c_i $中的最小顶点。进一步假设$ v_1 <v_2 < cdots <v_ ell $。展示如何通过一次保留这些索引中的最多两个索引来证明此数据在NL中正确的事实。

以下是一个更简单的问题的更多详细信息：验证无方向的图是否完全包含$ 10 sqrt {n} $连接的组件。我们保留一个柜台$ k $的顶点。假设顶点为$ 1 $至$ n $，对于$ t $，从$ 1 $到$ 10 sqrt {n} $，请执行以下操作：

1. 猜猜一个顶点$ v_t> v_ {t-1} $（其中$ v_0 = 0 $）。
2. 对于所有$ v <v_t $，请验证$ v $未连接到$ v_t $。
3. 对于每个$ v geq v_t $，猜猜$ v $是否已连接到$ v_t $，并验证猜测；对于连接到$ v_t $的每个顶点，增加$ k $。

如果最后$ k = n $，则所有顶点都被解释，并且该图完全包含$ 10 sqrt {n} $连接的组件。

我将解决实际问题解决的直接修改留给读者。