Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 1 di 36

REACHABILITY

Dato un grafo orientato con $n$ nodi e due nodi $x$ e $y$ : esiste un cammino da $x$ a $y$ ?

NLNL-completo

Un esempio, passo dopo passo

1 / 3

Individua partenza e arrivo. Il grafo orientato ha quattro nodi e gli archi A → B, B → C, A → C e C → D; A → C è l'arco curvo in alto. A e D hanno il bordo blu perché sono la partenza e l'arrivo. Cerchiamo un cammino da A a D. — 1. Individua partenza e arrivo
Il grafo orientato ha quattro nodi e gli archi $A \to B$ , $B \to C$ , $A \to C$ e $C \to D$ ; $A \to C$ è l'arco curvo in alto. $A$ e $D$ hanno il bordo blu perché sono la partenza e l'arrivo. Cerchiamo un cammino da $A$ a $D$ .

Scorri l'immagine o usa Avanti.

Una macchina nondeterministica indovina un cammino tenendo in memoria solo il nodo corrente e un contatore di $O(\log n)$ bit, quindi lavora in spazio logaritmico nondeterministico. Una visita del grafo risolve il problema in tempo polinomiale; la simulazione di Savitch usa spazio deterministico $O(\log^2 n)$ . Ogni problema di NL si riduce alla raggiungibilità nel grafo delle configurazioni.

Complemento e collegamenti

Il complemento chiede se

y

non è raggiungibile da

x

. Appartiene a

\mathrm{coNL} = \htmlData{term=NL}{\mathrm{NL}}

2-SAT si decide cercando cammini nel grafo delle implicazioni
il flusso si migliora cercando cammini nella rete residua

REACHABILITY in spazio logaritmico nondeterministico Teorema di Savitch (Teorema 7.5)

Domande e trappole d'esame

Il teorema di Savitch, $\mathrm{NSPACE}(f) \subseteq \mathrm{SPACE}(f^2)$ , si dimostra proprio risolvendo REACHABILITY sul grafo delle configurazioni. È la domanda di E26#1 e FE23#6 ( $\mathrm{NSPACE}(\log n)$ contro $\mathrm{SPACE}((\log n)^2)$ ).
Se la riduzione è così costosa da risolvere già il problema di partenza, non dimostra che questo stia nella classe del problema di arrivo.

Problemi del corso

1. Individua partenza e arrivo

2. Esplora i successori

3. Leggi il cammino