Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 4 di 36

MAX FLOW

Data una rete con capacità intere sugli archi, una sorgente $s$ , un pozzo $t$ e un intero $K$ : esiste un flusso da $s$ a $t$ di valore almeno $K$ ?

PP-completo

Nelle tracce · 4 domande

F02, domanda 1 G16, domanda 1 MZ22, domanda 7 E26, domanda 5

Un esempio, passo dopo passo

1 / 3

Leggi le capacità. Rete: s → a con capacità 3, a → t con 2, s → b con 2, b → t con 3. Obiettivo K = 4. — 1. Leggi le capacità
Rete: $s \to a$ con capacità 3, $a \to t$ con 2, $s \to b$ con 2, $b \to t$ con 3. Obiettivo $K = 4$ .

Scorri l'immagine o usa Avanti.

Si aumenta il flusso lungo cammini dalla sorgente al pozzo nella rete residua, rispettando capacità e conservazione. Scegliere cammini aumentanti minimi per numero di archi dà un numero polinomiale di aumenti, anche quando le capacità sono codificate in binario. Il valore massimo coincide con la capacità di un taglio minimo.

Complemento e collegamenti

Nessun complemento associato.

MAX FLOW è un caso di programmazione lineare
il flusso si migliora cercando cammini nella rete residua
PRIMES → MAX FLOW esiste, perché MAX FLOW è P-completo

$\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=P}{\mathrm{P}}$ e MAX-FLOW P-completo (riepilogo)

Domande e trappole d'esame

F02#1
È vero che MAX FLOW non è EXP-hard?
SÌ $\htmlData{term=problem:MAXFLOW}{\mathrm{MAX\ FLOW}} \in \htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ : se fosse EXP-hard avremmo $\htmlData{term=EXP}{\mathrm{EXP}} \subseteq \htmlData{term=P}{\mathrm{P}}$ .
G16#1
Supponiamo $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}$ . MAX FLOW è PH-completo?
NODarebbe $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}$ , contro $\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ .
E26#5
Esiste una riduzione da $\mathrm{co\text{-}QSAT}_3$ a MAX FLOW?
altro: solo se $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=P}{\mathrm{P}}$ $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}} \subseteq \htmlData{term=P}{\mathrm{P}}$ farebbe collassare PH a P.
MZ22#7
È vero che MAX FLOW non può essere deciso da una MdT deterministica in spazio polinomiale?
NO $\htmlData{term=problem:MAXFLOW}{\mathrm{MAX\ FLOW}} \in \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Problemi del corso

1. Leggi le capacità

2. Invia il flusso

3. Certifica il massimo