Überprüfen Sie, ob ein Digraph für $ n $ Scheitelpunkte genau $ 10 sqrt {n} $ stark angeschlossene Komponenten in NL enthält

Question

Ich studiere jetzt für einen Test in meinem Komplexitätskurs. Als ich frühere Prüfungen löste, sah ich die folgende Frage: Beweisen Sie, dass die Sprache $ l $ von allen gerichteten Grafiken auf $ n $ verticals, die genau $ 10 sqrt {n} $ enthalten, stark verbundene Komponenten enthalten, ist in $ nl $.

Wir haben in der Klasse gesehen, dass die Überprüfung, ob ein angegebenes Diagramm genau $ c $ stark verbunden ist $ Nl $ Wenn dann die Anzahl der erforderlichen SCC $ 10 sqrt {n} $ beträgt. Im Test war diese Frage 20 Punkte wert, also sollte es nicht zu schwer sein, also dachte ich, dass mir vielleicht etwas Wichtiges fehlt.

Answer 1

Hinweis: Angenommen, $ c_1, ldots, c_ ell $ sind die verbundenen Komponenten und $ v_i $ ist der minimale Scheitelpunkt in $ c_i $. Nehmen wir weiter an, dass $ v_1 <v_2 < cdots <v_ ell $. Zeigen Sie, wie Sie die Tatsache bestätigen, dass diese Daten in NL korrekt sind, indem Sie höchstens zwei dieser Indizes gleichzeitig aufbewahren.

Hier finden Sie einige weitere Details für ein etwas einfacheres Problem: Überprüfen Sie, ob ein ungerichteter Diagramm genau $ 10 sqrt {n} $ verbundene Komponenten enthält. Wir führen einen Schalter von $ k $ von Scheitelpunkten, die berücksichtigt werden. Angenommen, die Eckpunkte sind $ 1 $ bis $ n $ und für $ t $ von $ 1 $ bis 10 sqrt {n} $, machen Sie Folgendes:

1. Erraten Sie einen Scheitelpunkt $ v_t> v_ {t-1} $ (wobei $ v_0 = 0 $).
2. Überprüfen Sie für alle $ V <V_T $, dass $ v $ nicht mit $ v_t $ verbunden ist.
3. Raten Sie für jeden $ V Geq v_t $, ob $ v $ mit $ v_t $ verbunden ist oder nicht, und überprüfen Sie die Vermutung. Erhöhen Sie für jeden mit $ V_T $ verbundenen Scheitelpunkt $ k $.

Wenn am Ende $ k = n $ ist, werden alle Scheitelpunkte berücksichtigt, und das Diagramm enthält genau $ 10 sqrt {n} $ verbundene Komponenten.

Ich überlasse die einfache Modifikation, die das tatsächliche Problem dem Leser löst.