riduzione polinomiale

di Fabrizio Luccio - Enciclopedia della Scienza e della Tecnica (2008)

riduzione polinomiale

Fabrizio Luccio

Nello studio della complessità di algoritmi combinatori l’attenzione è focalizzata sulla classificazione dei problemi come polinomiali o esponenziali. L’esame si può limitare alla versione decisionale che è il nucleo di complessità di un problema e si propone di stabilire se il dato d’ingresso ha o meno una determinata proprietà, ovvero costituisce o meno una soluzione. Trattando, per es., di grafi i due problemi decisionali del ciclo euleriano e del ciclo hamiltoniano chiedono di stabilire se un grafo arbitrario G contiene un percorso chiuso che attraversa esattamente una volta tutti gli spigoli (ciclo euleriano) o tutti i vertici (ciclo hamiltoniano). Si definiscono la classe P come quella di tutti i problemi per i quali la decisione richiesta può essere presa in tempo polinomiale nella dimensione dei dati, e la classe NP come quella di tutti i problemi per cui tale decisione può richiedere tempo esponenziale ma è possibile verificare in tempo polinomiale che una soluzione proposta ha le caratteristiche desiderate. Il problema del ciclo euleriano appartiene a P, cioè si può decidere in tempo polinomiale se esiste un ciclo euleriano in C; quello del ciclo hamiltoniano appartiene a NP perché è possibile verificare in tale tempo che un dato ciclo è hamiltoniano, anche se determinarne l’esistenza dove non sia dato richiede tempo esponenziale. Si ha P⊆NP. Il meccanismo di riduzione polinomiale consente di stabilire la difficoltà dei problemi in NP, nel senso seguente. Un problema P1 si riduce in tempo polinomiale a un problema P2, in formule P1≤PP2, se esiste una funzione f calcolabile in tempo polinomiale tale che X è una soluzione di P1 se e solo se f(X) è una soluzione di P2. Conoscendo un algoritmo A di soluzione per P2 e la funzione f relativa alla coppia P1, P2, si può risolvere P1 trasformando ogni dato X di P1 in un dato f(X) di P2 e applicando l’algoritmo A a f(X). Ne segue che se P2 appartiene a P anche P1 appartiene a P. I problemi ‘più difficili’ in NP sono pertanto così definiti: un problema P è NP-completo se P∈NP e P′≤PP per ogni P′∈NP.

→ Complessità algoritmica

Vedi anche
equazione matematica 1. Definizioni Si chiama equazione un’uguaglianza tra due espressioni contenenti una o più variabili ovvero una o più funzioni o anche enti di natura più generale ( incognite dell’equazione); se essa è soddisfatta, qualunque sia la determinazione delle variabili o delle funzioni o degli enti ... algebra Uno dei rami fondamentali delle scienze matematiche: in senso lato l’algebra studia le operazioni, definite in un insieme, che godono di proprietà analoghe a quelle delle ordinarie operazioni dell’aritmetica. Con significato specifico è sinonimo di sistema ipercomplesso. ● La parola al-giabr è usata ... combinatòria combinatòria Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, particolarmente importanti per i calcolatori elettronici, tra le quali i loop, i monoidi, ... grafo Nel linguaggio scientifico, struttura relazionale formata da un insieme finito di oggetti detti nodi o vertici, e da un insieme di relazioni tra coppie di oggetti dette archi o spigoli. Per indicare un grafo viene utilizzata una notazione del tipo: G(N, A), dove N indica l’insieme dei nodi e A l’insieme ...
Categorie
Tag
Altri risultati per riduzione polinomiale
  • Bernstein, polinomi di
    Enciclopedia della Matematica (2013)
    Bernštein, polinomi di in analisi, particolari polinomi che approssimano una funzione continua in un intervallo. Più precisamente, data una funzione ƒ(x) definita nell’intervallo [0, 1], i polinomi di Bernštein relativi a tale funzione sono i polinomi dove è il coefficiente binomiale. Il teorema ...
  • polinomio
    Enciclopedia on line
    In matematica, somma di monomi (in senso proprio, solo con riferimento a monomi interi), detti termini del p.: binomio, trinomio, quadrinomio ecc., è un polinomio rispettivamente di 2, 3, 4 ecc. termini; coefficienti di un p. sono i coefficienti dei suoi monomi; grado di un p. rispetto a una lettera ...
  • polinomio
    Dizionario delle Scienze Fisiche (1996)
    polinòmio [Comp. di poli- e -nomio di binomio] [ANM] Somma di più monomi, detti termini del p., i cui coefficienti sono detti coefficienti del p.; grado di un p. rispetto a una variabile è il grado massimo dei monomi rispetto a tale variabile e grado complessivo è il grado massimo dei monomi rispetto ...
  • POLINOMIO
    Enciclopedia Italiana (1935)
    Giovanni Lampariello . Termine in uso nell'algebra per indicare la somma di due o più monomî (v. monomio), che non siano tutti simili tra loro. Se dopo aver fatto la riduzione degli eventuali termini simili, il polinomio comprende due o tre termini, esso si chiama rispettivamente binomio o trinomio. ...
Vocabolario
polinomiale
polinomiale agg. [der. di polinomio]. – In matematica, relativo a un polinomio.
riduzióne
riduzione riduzióne (ant. reduzióne) s. f. [dal lat. reductio -onis «il ricondurre», der. di reducĕre: v. ridurre]. – 1. L’azione, l’operazione di ricondurre, di ricollocare o far tornare al luogo o al posto proprio, normale. È ormai usato,...