Definizione di NP-durezza per problemi non decisionali
A quanto ho capito, il termine "durezza NP" è applicabile anche quando parliamo di problemi di ottimizzazione o di ricerca (ovvero restituire l'assegnazione soddisfacente per 3-SAT). Come definiamo formalmente la durezza NP per tali problemi? La definizione standard:
Il problema è NP-difficile quando qualsiasi problema da NP è riducibile in tempo polinomiale a questo problema
non ha molto senso, a causa di come viene definita la riduzione:
Lingua$A$è tempo polinomiale riducibile a$B$se esiste una funzione calcolabile poli-tempo$f$, tale che$x \in A$se$f(x) \in B$.
Il problema è che$B$(es. il nostro problema di ricerca) non definisce una lingua (potrebbero esserci altre definizioni equivalenti, come$A(x) \in \{true, false\}$, ma porteranno agli stessi problemi).
Il mio amico ha suggerito che possiamo definire una seconda funzione calcolabile poli-tempo$g^{-1}$, che converte una "risposta" per$B$di cui rispondere$A$:$x \in A$se$g^{-1}(B(f(x)))$è$true$, dove$B(y)$è una risposta corretta per$y$. Questo ha senso, ma non l'ho mai visto.
Allora, qual è la definizione standard? Per una risposta, chiederei anche una citazione appropriata (non a Wikipedia o diapositive casuali).
Risposte
C'è un leggero abuso di notazione in corso. Diciamo che una funzione$f$è NP-difficile se$f\in FP$implica$P=NP$. Ad esempio, se$L$è NP completo e$M_L(x,y)$è un verificatore per$L$, quindi qualsiasi funzione$f$quali mappe$x$a certi$y$tale che$M_L(x,y)$ogni volta che tale$y$esiste è ovviamente NP-difficile in questo senso. Di solito non si parla di effettive riduzioni in questo contesto, ma è naturale dirlo$L$riduce al calcolo$f$è come dire che esiste una macchina oracolo del tempo polinomiale$M^f$con accesso a$f$che decide$L$.
Vedi anche lo zoo sulla classe FNP. Il fatto che i problemi di "funzione NP" siano definiti relativamente a uno specifico verificatore introduce qualche difficoltà quando si parla di riduzione dalla ricerca alla decisione.
Non troverai un riferimento per "la definizione standard" di durezza NP. Alcuni autori limitano la nozione "NP-hard" solo ai problemi decisionali e usano la definizione di riduzione che menzioni nella tua domanda (che a volte viene definita "riduzione di Karp" o "riduzione di molti uno"). Altri autori usano il termine in modo più approssimativo ed estendono la nozione ad altri tipi di problemi (come i problemi di ricerca o di ottimizzazione). Puoi trovare un po' di retroscena storica nel "Post scriptum sui problemi NP-difficili" di Donald Knuth.
L'articolo di wikipedia ne discute esplicitamente (e fornisce alcuni riferimenti):
Un problema decisionale H è NP-difficile quando per ogni problema L in NP esiste una riduzione multiuno in tempo polinomiale da L a H. [...]
Un'altra definizione è richiedere che ci sia una riduzione in tempo polinomiale da un problema NP-completo G a H. [...] Stranamente, non restringe la classe NP-difficile ai problemi decisionali, e include anche problemi di ricerca o problemi di ottimizzazione.
Il suggerimento del tuo amico ha alcune somiglianze con le riduzioni di Cook, che a volte sono usate come definizione più generica di "durezza NP". Il suggerimento del tuo amico cattura bene ciò che le persone di solito intendono quando parlano di un problema di ottimizzazione che è NP-difficile.