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 [...] 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 ...
Leggi Tutto
Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] ∈L1 se e solo se f(v)∈L2. Si dice allora che P1 si riduce a P2, e si indica con P1⇒P2. Si noti che la riduzione polinomiale è transitiva, cioè P1⇒P2 e P2⇒P3 implicano P1⇒P3.
Se P1⇒P2, un algoritmo A2 per risolvere P2 può essere usato per risolvere P1 ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] un numero composto o è un numero primo (test di primalità), un problema per il quale non è, ancora oggi, noto alcun algoritmo polinomiale.
Definiamo certificato di non primalità di un intero n un altro intero m, con 1〈m〈n, dotato di proprietà tali da ...
Leggi Tutto
Visione artificiale
Pietro Parodi
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
Vincent Torre
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
La visione artificiale, [...] problema X si dice completo per una classe C se ogni problema appartenente a C si può trasformare in X con complessità polinomiale. In altri termini, nessun problema in C è 'più difficile' di X. Se esiste un algoritrno che risolve X con complessità O ...
Leggi Tutto
complessità Caratteristica di un sistema (perciò detto complesso), concepito come un aggregato organico e strutturato di parti tra loro interagenti, in base alla quale il comportamento globale del sistema [...] . Dati ora due problemi R e Q si dice che «R si riduce a Q» (e si indica con R ∝ Q), se esiste un algoritmo polinomiale che associa a ogni istanza di R un’istanza di Q in modo tale che la soluzione dell’istanza di Q fornisce la soluzione della ...
Leggi Tutto
Matematica: problemi aperti
Claudio Procesi
Prima di parlare dei problemi aperti nella matematica è bene riflettere su quelli che ne hanno segnato la storia passata. Sono infatti proprio questi che [...] la minima lunghezza di un programma che calcola f. Detto Z(f) il numero di radici intere di f, la domanda è se questo sia polinomiale in τ(f) e cioè se esistano costanti A,c tali che per ogni polinomio intero f(t)∈ℤ[t] si abbia
[14] formula.
Il ...
Leggi Tutto
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] che si tratta di un problema NP-completo, nel senso che ogni problema in NP si può ridurre a questo in un tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma ciò non è stato ancora dimostrato e anzi costituisce uno dei problemi ...
Leggi Tutto
Previsioni economiche
Giovanni De Cindio
di Giovanni De Cindio
Previsioni economiche
Presupposti storici
La pratica sistematica delle previsioni economiche, cioè dell'attività di previsione avente [...] nel tempo sulla variabile dipendente. Le forme più usate di funzioni a ritardi distribuiti sono quelle cosiddette aritmetica, polinomiale, geometrica ed esponenziale.In generale non si conosce la struttura dei ritardi, che pertanto può avere forme ...
Leggi Tutto
INFORMAZIONE, SCIENZA DELLA
Roman Tirler
Pierluigi Ridolfi
Stefano Ceri e Alfonso Fuggetta
Tecnologie della comunicazione di Roman Tirler
Sommario: 1. Introduzione. 2. Tecniche di comunicazione dati: [...] cui l'algoritmo deve operare; la complessità viene espressa come una funzione f (n). Se f è una funzione polinomiale, il problema viene classificato come trattabile, cioè risolubile in un tempo comunemente accettabile; viceversa, se f è una funzione ...
Leggi Tutto
Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori [...] : nel 1994 Shor ha infatti dimostrato che nel modello di c. quantistico tale problema può essere risolto in tempo polinomiale, risultato che non viene ritenuto possibile in un modello di c. classico. Tale scoperta ha potenzialmente una grande valenza ...
Leggi Tutto