Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 25 di 36

EXACT TSP

Date le distanze tra le città e un intero $B$ : il giro più corto ha lunghezza esattamente $B$ ?

DPDP-completo

Nelle tracce · 3 domande

F14, domanda 2 G20v5, domanda 7 GE23, domanda 7

Un esempio, passo dopo passo

1 / 3

Leggi il valore richiesto. Tre città: AB = 2, BC = 3, CA = 4. Chiediamo se l’ottimo è B = 9. — 1. Leggi il valore richiesto
Tre città: $AB = 2$ , $BC = 3$ , $CA = 4$ . Chiediamo se l’ottimo è $B = 9$ .

Scorri l'immagine o usa Avanti.

L’ottimo è $B$ se e solo se esiste un giro di costo $\le B$ e non esiste un giro di costo $\lt B$ . Il primo controllo è di tipo NP, il secondo di tipo coNP. Trovare un giro da $B$ non certifica da solo che sia ottimo: occorre escludere giri più economici.

Complemento e collegamenti

Nessun complemento associato.

" $\le B$ " contro " $= B$ ": NP contro DP
$\htmlData{term=problem:EXACT}{\mathrm{EXACT\ TSP}} = \bigl(\htmlData{term=problem:TSPD}{\mathrm{TSP(D)}}\ \text{con}\ B\bigr) \cap \bigl(\htmlData{term=problem:COTSP}{\mathrm{co\text{-}TSP(D)}}\ \text{con}\ B - 1\bigr)$
EXACT TSP è DP-completo per riduzione da SAT-UNSAT

EXACT TSP è NP-hard (varianti di TSP)Altri problemi DP-completi

Domande e trappole d'esame

GE23#7
EXACT TSP è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -hard?
altro: solo se $\htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ : essere $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -hard darebbe $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=DP}{\mathrm{DP}}$ .
G20v5#7
È vero che EXACT TSP non è $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ -hard?
NO $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=DP}{\mathrm{DP}}$ : un DP-completo è anche NP-hard.

Problemi del corso

1. Leggi il valore richiesto

2. Trova un giro entro $B$

3. Escludi giri sotto $B$