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. Grafo orientato con archi A → B, B → C, A → C e C → D. Cerchiamo un cammino da A a D. — 1. Individua partenza e arrivo
Grafo orientato con archi $A \to B$ , $B \to C$ , $A \to C$ e $C \to D$ . Cerchiamo un cammino da $A$ a $D$ .

Scorri l'immagine o usa Avanti.

Una macchina nondeterministica indovina un cammino mantenendo il nodo corrente e un contatore di $O(\log n)$ bit. Questo dà un algoritmo 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)$ ).
Il costo della riduzione conta: una trasformazione che risolve già il problema iniziale non dimostra la sua appartenenza alla classe del problema di arrivo.

Problemi del corso

1. Individua partenza e arrivo

2. Esplora i successori

3. Leggi il cammino