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 [...] 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 può essere descritto, in termini di legami ingresso-uscita, dalle equazioni
dove A è una matrice, B è un vettore colonna e ...
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 [...] cui il principio di indeterminazione di Heisenberg e l'equazione di Schrödinger. Lo sviluppo di una macchina di di c. quantistico tale problema può essere risolto in tempo polinomiale, risultato che non viene ritenuto possibile in un modello di c ...
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, [...] faccia.f3; perciò, esso è dietro la faccia f1, e vale l'equazione a1x4+b1y4+z4+c1 > 0. Se in base all'etichettatura è possibile appartenente a C si può trasformare in X con complessità polinomiale. In altri termini, nessun problema in C è 'più ...
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 [...] ogni problema in NP si può ridurre a questo in un tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma una parola su A per ciascuna delle incognite x∈X. Per esempio, l'equazione ax=yb ha la soluzione x=b, y=a. Gennady S. Makanin ha ...
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 [...] prima di tutto che la Nullstellensatz (in forma equivalente) afferma che un sistema f1(x1,…,xn)=0,…,fk(x1,…,xn)=0 di equazionipolinomiali a coefficienti complessi non ha una soluzione fi(ζ1,…,ζn)=0 se e solo se esistono polinomi gi con ∑ki=1gifi=1 ...
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, [...] 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 una o più dimensioni e di risoluzione intera di equazioni. Se si passa a una più generale forma risolvente ...
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 [...] a ritardi distribuiti sono quelle cosiddette aritmetica, polinomiale, geometrica ed esponenziale.In generale non si che permettono di introdurre differenze nel coefficiente dell'equazione di base per consentirne l'adattamento ai diversi sottogruppi ...
Leggi Tutto