problemi decisionali vs problemi “reali” che non sono sì-o-no

Question

ho letto in molti luoghi che alcuni problemi sono difficili da approssimare (è NP-hard per approssimare loro). Ma approssimazione non è un problema di decisione: la risposta è un numero reale e non Sì o No. Anche per ciascun fattore approssimazione desiderata, ci sono molte risposte che sono corrette e molti che sono sbagliate, e questo cambia con il fattore di approssimazione desiderato

Quindi, come si può dire che questo problema è NP-hard?

(ispirato il secondo punto in Quanto è difficile contare il numero di percorsi semplici tra due nodi in un diretto grafico? )

Answer 1

Come hai detto, non v'è alcuna decisione da prendere, sono necessarie quindi nuove classi di complessità e nuovi tipi di riduzioni per arrivare ad una opportuna definizione di NP-difficile per ottimizzazione-problemi .

Un modo per farlo è quello di avere due nuove classi NPO e PO che contengono ottimizzazioni problemi e mimica, naturalmente, le classi < problemi strong> NP e P per la decisione. Le nuove riduzioni sono necessari pure. Poi possiamo ricreare una versione di NP-difficile per problemi di ottimizzazione lungo le linee che ha avuto successo per problemi decisionali. Ma prima dobbiamo essere d'accordo quello che un Ottimizzazione problemi è.

Definizione: Sia $ O = (X, L, F, OPT) $ essere un Ottimizzazione problemi . $ X $ è l'insieme di ingressi o le istanze adatto codificato come stringhe. $ L $ è una funzione che mappa ogni istanza $ x \ in X $ su un insieme di stringhe, soluzioni fattibili di esempio $ x $. Si tratta di un insieme perché ci sono molte soluzioni per l'ottimizzazione-problema. Così rifugio un funzione obiettivo $ f $ che ci dice per ogni coppia $ (x, y) $ $ y \ a L (x) $ di esempio e la soluzione la sua costo o valore . $ Opt $ ci dice se stiamo ingrandimento o la riduzione.

Questo ci permette di definire ciò che un soluzione ottimale è: Sia $ y_ {opt} \ a L (x) $ essere il soluzione ottimale di un'istanza $ x \ in x $ di un'ottimizzazione problemi $ O = (x, L, F, oPT) $ con $$ f (x, y_ {opt}) = opt \ {f (x, y ') \ mid y' \ a L (x) \} $$. La soluzione ottimale è spesso indicato con $ y ^ * $.

Ora possiamo definire la classe NPO : Let $ NPO $ l'insieme di tutti i ottimizzazione-problemi $ O = (X, L, F, OPT) $ con:

1. $ X \ in P $
2. C'è un polinomio $ p $ con $ | y | \ le p (| x |) $ per tutte le istanze $ x \ in X $ e tutte le soluzioni praticabili $ y \ a L (x) $. Inoltre v'è un algoritmo deterministico che decide in tempo polinomiale se $ y \ a L (x) $.
3. $ f $ può essere valutata in tempo polinomiale.

L'intuizione alla base è:

1. possiamo verificare in modo efficiente se $ x $ è in realtà un'istanza valida del nostro problema di ottimizzazione.
2. Le dimensioni delle soluzioni possibili è delimitata polinomiale nella dimensione degli ingressi, e possiamo verificare in modo efficiente se $ y \ in L (x) $ è una soluzione fesible dell'istanza $ x $.
3. Il valore di una soluzione di $ y \ a L (x) $ è possibile determinare in modo efficiente.

Questa specchi come viene definito $ NP $, ora PO :. Let $ PO $ l'insieme di tutti i problemi da $ NPO $ che possono essere risolti da un algoritmo deterministico in tempo polinomiale

Ora siamo in grado di definire ciò che vogliamo chiamare un approssimazione-algoritmo : un approssimazione-algoritmo di un'ottimizzazione problemi $ O = (X, L, f, opt) $ è un algoritmo che calcola una soluzione praticabile $ y \ in L (x) $ per un'istanza $ x \ in x $.

Nota:. Che noi non chiediamo un ottimale soluzione che solo ciò che di avere una fattibile un

Ora abbiamo due tipi di errori: Il errore assoluto di una soluzione ammissibile $ y \ a L (x) $ di un'istanza $ x \ in X $ dell'ottimizzazione-problema $ O = (x, L, F, opt) $ è $ | f (x, y) -f (x, y ^ *) |. $

Chiamiamo l'errore assoluto di un'approssimazione-algoritmo di $ A $ per l'ottimizzazione problemi $ O $ delimitata da $ k $ se l'algoritmo $ A $ calcola per ogni x \ in X $ una soluzione fattibile esempio $ con una errore assoluto delimitata da $ k $.

Esempio: Secondo il teorema di Vizing index cromatica di un grafico (il numero di colori nel bordo colorare con il minor numero di colori usati) è o $ \ Delta $ o $ \ Delta + 1 $, dove $ \ Delta $ è il grado nodo di massima. Dalla dimostrazione del teorema di approssimazione-algoritmo può essere concepito che calcola un bordo colorazione con $ \ Delta + 1 $ colori. Di conseguenza abbiamo un'approssimazione-algoritmo per la mathsf $ \ {minimo-EdgeColoring} $ - Problema dove l'errore assoluto is delimitata da $ 1 $.

Questo esempio è un'eccezione, piccoli errori assoluti sono rari, così definiamo il errore relativo $ \ epsilon_A (x) $ del ravvicinamento algoritmo $ A $ su istanza $ x $ della ottimizzazione-problema $ O = (x, L, F, oPT) $ con $ f (x, y)> 0 $ per tutti i $ x \ in x $ e $ y \ a L (x) $ di essere

$$ \ epsilon_A (x): = \ begin {casi} 0 & f (x, A (x)) = f (x, y ^ *) \\\ frac {| f (x, A (x)) -f (x, y ^ *) |} {\ max \ {f (x, A (x)), f (x, y ^ *) \}} & f (x, A (x)) \ ne f ( x, y ^ *) \ end {casi} $$

dove $ A (x) = y \ in L (x) $ è la soluzione ammissibile calcolata mediante il ravvicinamento algoritmo $ A $.

Ora possiamo definire approssimazione-algoritmo di $ A $ per l'ottimizzazione problemi $ O = (X, L, F, OPT) $ per essere un $ \ delta $ -approximation-algoritmo per $ O $ se l'errore relativo $ \ epsilon_A (x) $ è delimitata da $ \ delta \ ge 0 $ per ogni istanza $ x \ in x $, quindi $$ \ epsilon_A (x) \ le \ delta \ qquad \ forall x \ in X. $$

La scelta di $ \ max \ {f (x, A (x)), f (x, y ^ *) \} $ nel denominatore della definizione della errore relativo è stato scelto per fare la simmetrica definizione per massimizzare e minimizzare. Il valore dell'errore relativo $ \ epsilon_A (x) \ in [0,1] $. In caso di problemi massimizzare il valore della soluzione non è mai inferiore a $ (1- \ epsilon_A (x)) \ cdot f (x, y ^ *) $ e mai più grande di $ 1 / (1- \ epsilon_A (x) ) \ cdot f (x, y ^ *) $ per un problema di minimizzazione.

Ora si può chiamare un'ottimizzazione-problema $ \ delta $ -approximable se c'è un $ \ delta $ -approximation-algoritmo di $ A $ per $ O $ che viene eseguito in tempo polinomiale.

Non vogliamo guardare l'errore per ogni istanza $ x $, guardiamo solo al caso peggiore. Così definiamo $ \ epsilon_A (n) $, massima relativ errore di approssimazione-algoritmo di $ A $ per l'ottimizzazione problemi $ O $ per essere $$ \ epsilon_A (n) = \ sup \ {\ epsilon_A (x) \ metà | x | \ le n \}. $$

Dove $ | x |. $ Dovrebbe essere la dimensione dell'istanza

Esempio: Un abbinamento massimo in grafico può essere trasformato in un nodo minima copertina $ C $ aggiungendo tutti i nodi incidenti dall'abbinamento al coperchio vertice. Così $ 1/2 \ cdot | C | $ bordi sono coperti. Come ogni coperchio vertice compreso l'ottimale one deve avere uno dei nodi di ogni bordo coperto, altrimenti potrebbe essere migliorato, abbiamo $ 1/2 \ cdot | C | \ cdot f (x, y ^ *) $. Ne consegue che $$ \ frac {| C | -f (x, y ^ *) {} | C |} \ le \ frac {1} {2} $$ Così l'algoritmo greedy per una corrispondenza massima è un algoritmo -approximatio $ 1/2 $ a $ \ {mathsf minimal-problema di copertura dei vertici} $. Quindi $ \ {mathsf minimal-problema di copertura dei vertici} $ è di $ 1/2 $ -approximable.

Purtroppo l'errore relativo non è sempre la migliore idea di qualità per un'approssimazione come il seguente esempio dimostra:

Esempio: un semplice avido-algoritmo può approssimare $ \ {mathsf minima-SetCover} $. Un'analisi mostra che $$ \ frac {| C |} {| C ^ * |} \ le H_n \ le 1+ \ ln (n) $$ e quindi $ \ {mathsf minima-SetCover} $ sarebbe $ \ frac {\ ln (n) {} 1+ \ ln (n)} $ -. approssimabili

Se l'errore relativo è vicino a $ 1 $ la seguente definizione è vantaggioso.

Sia $ O = (X, L, F, OPT) $ sia un'ottimizzazione problemi con $ f (x, y)> 0 $ per tutti i $ x \ in X $ e $ y \ a L (x) $ e $ a $ un'approssimazione-algoritmo per $ O $. ravvicinamento Quota $ R_A (x) $ di soluzione ammissibile $ A (x) = y \ in L (x) $ dell'istanza $ x \ in X $ è $$ R_A (x) = \ begin {casi} 1 & f (x, A (x)) = f (x, y ^ *) \\\ max \ left \ { \ frac {f (x, A (x))} {f (x, y ^ *)}, \ frac {f (x, y ^ *)} {f (x, A (x))} \ right \ } & f (x, A (x)) \ ne f (x, y ^ *) \ end {casi} $$

Come prima che noi chiamiamo un'approssimazione-algoritmo di $ A $ un $ R $ -approximation-algoritmo per l'ottimizzazione problemi $ O $ se il ravvicinamento-ratio $ R_A (x) $ è delimitata da $ r \ GE1 $ per ogni ingresso $ x \ in x $. $$ R_A (x) \ le r $$ E ancora una volta, se abbiamo un $ R $ -approximation-algoritmo di $ A $ per l'ottimizzazione problemi $ O $ allora $ O $ è chiamato $ r $ -approximable . Anche in questo caso ci interessa solo per il caso peggiore e definire il massima approssimazione-ratio $ R_A (n) $ di essere $$ R_A (n) = \ sup \ {R_A (x) \ metà | x | \ le n \}. $$ Pertanto il ravvicinamento-rapporto è maggiore di $ 1 $ per soluzioni subottimali. cosìsoluzioni migliori hanno rapporti più piccole. Per $ \ {mathsf minima-SetCover} $ ora possiamo scrivere che si tratta di $ (1+ \ ln (n)) $ - approssimabili. E in caso di $ \ {mathsf minima-problema di copertura dei vertici} $ sappiamo dell'esempio precedente che è $ 2 $ -approximable. Fra l'errore relativo e approssimazione Quota abbiamo rapporti semplici: $$ R_A (x) = \ frac {1} {1- \ epsilon_A (x)} \ qquad \ epsilon_A (x) = 1- \ frac {1} {R_A (x)}. $$

Per piccoli scostamenti dai valori ottimali $ \ epsilon <1/2 $ e $ r <2 $ l'errore relativo è vantaggioso rispetto alla approssimazione-rapporto, che mostra la sua forza di grandi deviazioni $ \ epsilon \ ge 1/2 $ e $ r \ ge 2 $.

Le due versioni di $ \ alpha $ -approximable non si sovrappongono come una versione ha sempre $ \ alpha \ le 1 $ e l'altro $ \ alpha \ ge 1 $. Il caso $ \ alpha = 1 $ non è problematico in quanto questo viene raggiunto solo da algoritmi che producono una soluzione esatta e di conseguenza non devono essere trattate come approssimazione algoritmi.

Un'altra classe appare spesso APX . Si definisce come l'insieme di tutti i ottimizzazione-problemi $ O $ da $ NPO $ che porto un $ R $ -approximation-algoritmo con $ r \ GE1 $ che viene eseguito in tempo polinomiale.

Siamo quasi attraverso. Vorremmo copiare le idee di successo di riduzioni e completezza dalla teoria della complessità. L'osservazione è che molti decisione NP-hard varianti di ottimizzazione-problemi sono riducibili l'uno all'altro, mentre i loro varianti di ottimizzazione hanno proprietà diverse per quanto riguarda la loro approssimabilità. Ciò è dovuto al polynomialtime-Karp riduzione utilizzato in riduzioni NP-completezza, che non mantiene la funzione obiettivo. E anche se le funzioni obiettivo è conservata la polynomialtime-Karp-riduzione può cambiare la qualità della soluzione.

Quello che ci serve è una versione più forte della riduzione, che mappa non solo le istanze dall'ottimizzazione-problema $ O_1 $ alle istanze di $ O_2 $, ma anche buone soluzioni da $ O_2 $ torna a buone soluzioni da $ O_1 $.

Quindi definiamo ravvicinamento preservano riduzione per due ottimizzazione-problemi $ O_1 = (X_1, L_1, f_1, opt_1) $ e $ O_2 = (x_2, L_2, F_2, opt_2) $ a partire da $ NPO $. Chiamiamo $ O_1 $ $ AP $ -reducible a $ O_2 $, scritto da $ O_1 \ le_ {AP} O_2 $, se ci sono due funzioni $ G $ e $ h $ e una costante $ C $ con:

1. $ g (x_1, r) \ in x_2 $ per tutti i $ x_1 \ in X_1 $ e razionale $ r> 1 $
2. $ L_2 (g (x, R_1)) \ ne \ emptyset $ se $ L_1 (x_1) \ ne \ emptyset $ per tutti i $ x_1 \ in X_1 $ e $ razionale r> 1 $
3. $ h (x_1, y_2, r) \ a L_1 (x_1) $ per tutti i $ x_1 \ in X_1 $ e razionale $ r> 1 $ per tutte $ y_2 \ a L_2 (g (x_1, r)) $
4. Per $ fissa r $ entrambe le funzioni $ g $ e $ h $ può essere calcolato da due algoritmi in tempo polinomiale nella lunghezza dei loro ingressi.
5. Abbiamo $$ F_2 (g (x_1, r), y_2) \ le r \ Rightarrow f_1 (x_1, h (x_1, y_2, r)) \ le 1 + c \ cdot (r-1) $$ per tutti $ x_1 \ in x_1 $ e razionale $ r> 1 $ per tutte $ y_2 \ a L_2 (g (x_1, r)) $

In questa definizione $ g $ e $ h $ dipendono dalla qualità della soluzione $ R $. Così per diverse qualità le funzioni possono differire. Questa generalità non è sempre necessario e abbiamo appena lavoro con $ g (x_1) $ e $ h (x_1, y_2) $.

Ora che abbiamo una nozione di una riduzione per l'ottimizzazione-problemi che finalmente in grado di trasferire molte cose che sappiamo dalla teoria della complessità. Per esempio, se sappiamo che $ O_2 \ in APX $ e mostriamo che $ O_1 \ le_ {AP} O_2 $ ne consegue che $ O_1 \ in APX $ troppo.

Finalmente possiamo definire cosa intendiamo per $ \ mathcal {C} $ - duro e $ \ mathcal {C} $ - completa per l'ottimizzazione-problemi:

Sia $ O $ essere un'ottimizzazione-problema da $ NPO $ e $ \ mathcal {C} $ una classe di ottimizzazione-problemi da $ NPO $ allora $ O $ è chiamato $ \ mathcal {C} $ -Hard , rispetto a $ \ le_ {AP} $ se per ogni $ O '\ in \ mathcal {C} $ $ O' \ le_ {AP} O $ detiene.

In questo modo ancora una volta abbiamo una nozione di difficile problema nella classe. Non sorprende un $ \ mathcal {C} $ - difficile problema si chiama $ \ mathcal {C} $ - completo rispetto a $ \ le_ {AP} $ se si tratta di un elemento di$ \ Mathcal {C} $.

Così ora possiamo parlare di $ NPO $ -completness e $ APX $ -completness ecc E, naturalmente, ora stiamo chiesto di esibire un primo $ NPO $ problema -Complete che assume il ruolo di $ \ {mathsf SAT } $. Viene quasi naturale, che $ \ {mathsf Weighted-Soddisfacibilità} $ può essere dimostrato di essere $ NPO $ -Complete. Con l'aiuto del PCP-teorema si può anche dimostrare che $ \ mathsf {max-3SAT} $ è $ APX $ -Complete.

Answer 2

Di solito ciò che è indicato è la NP-difficile di una versione "Gap" del problema. Ad esempio, si supponga che si desidera mostrare che è difficile per coprire approssimativa SET per meno di un fattore di 2.

Si definisce la seguente istanza "promessa" di impostare la copertina che chiameremo 2-GAP-SET-COVER:

Fissare un numero $ \ ell $. 2-GAP-SET-COVER consiste di tutte le istanze di copertura set in cui la dimensione della copertura insieme ottimale è o:

• al massimo $ \ ell $
• almeno $ 2 \ ell $

Supponiamo si dimostra che il problema di decidere quale dei due casi un problema cade in è NP-completo. Poi abbiamo dimostrato che il ravvicinamento stabilito della copertura entro un fattore 2 è NP-difficile, perché abbiamo potuto utilizzare un algoritmo per distinguere questi due casi.

Answer 3

Le due risposte esistenti sono molto informativo, ma non credo che una di esse risponde realmente alla domanda, che è, "Come può un problema che non è nemmeno un problema decisionale essere NP-hard, quando NP è una classe di problemi decisionali? "

La risposta è da ricordare che cosa significa NP-difficile. Un problema $ L $ è NP-hard in un qualche tipo di riduzione, se ogni problema in NP può essere ridotto a $ L $. (E $ L $ è NP-completo se è NP-hard e in NP.) Informalmente, NP-hard significa "Se potessi risolvere questo problema, ho potuto risolvere tutto in NP", anche se il problema si sta parlando non è in NP. NP-difficile non richiede l'adesione di NP, ma ha bisogno il diritto nozione di riduzione.

Alcuni esempi.

1. Qualsiasi NEXPTIME-complete problema $ L $ è NP-hard in polinomiale in tempo riduzioni molti-uno. Qualsiasi problema in NP è in NEXPTIME così è riducibile a $ L $ per definizione. Dalla gerarchia teorema tempo, $ L $ non può essere in NP, quindi $ L $ non è NP-completo.
2. #SAT è il problema del calcolo del numero di soddisfare le assegnazioni alle formule CNF. Non è chiaramente in NP perché, come si osserva, NP è una classe di problemi di decisione e #SAT non è uno di quelli. Tuttavia, #SAT è NP-hard in riduzioni di Turing polinomiale in tempo perché possiamo ridurre SAT ad esso. Dato un esempio SAT, ci chiediamo quanti incarichi soddisfare ci sono: se c'è almeno una, diciamo "satisfiable"; in caso contrario, "insoddisfacibile".
3. Sia APPROXSAT essere il problema del calcolo un numero che è all'interno di un fattore dieci del numero di incarichi che soddisfano ad un CNF formula $ \ varphi $. Giusto per essere fastidioso, diciamo che si è permesso di giù turno in modo, se $ \ varphi $ ha, diciamo, tre assegnazioni soddisfacenti, l'algoritmo è permesso di pensare "0.3" e rotonda che fino a zero. Questo è NP-hard in riduzioni di Turing polinomiale in tempo perché possiamo ancora ridurre la SAT ad esso. Data una formula CNF $ \ varphi $, per chiedere il numero di incarichi che soddisfano a $ \ varphi '= \ varphi \ wedge (Z_1 \ vee \ dots \ vee Z_ {10}) $, dove il $ Z_i $ sono nuove variabili. $ \ Varphi '$ è soddisfacibile se, e solo se, $ \ varphi $ è, ma $ \ varphi' $ è garantito per avere più di 1.000 assegnazioni che soddisfano, se ne ha. Quindi, $ \ varphi $ è soddisfacibile se, e solo se, l'algoritmo APPROXSAT dice che $ \ varphi '$ ha almeno 100 assegnazioni soddisfacente.