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à 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
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, [...] al tempo stesso, si conoscono solo delimitazioni inferiori di complessità polinomiali. Alcuni esempi di problemi di tale tipo sono la risolubilità di un sistema di equazioni lineari a variabili intere, la soddisfattibilità di un'espressione booleana ...
Leggi Tutto
L'evoluzione temporale dei sistemi - in particolare di quelli deterministici, cioè tali che la conoscenza del sistema a un dato istante ne determina tutta l'evoluzione futura - è stata negli ultimi decenni [...] dei pianeti, ovvero dimostrarono l'assenza di termini polinomiali nel tempo almeno fino al terzo ordine nelle masse compiuta intorno al 1990. Laskar sostituì al sistema di equazioni di Newton il cosiddetto sistema secolare introdotto da Lagrange, ...
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
Chimica quantistica
Frank Jensen
La materia è costituita da nuclei atomici e da elettroni che interagendo formano gli atomi e le molecole, i quali a loro volta danno origine alla materia inorganica, [...] funzione d'onda mediante le consuete funzioni matematiche polinomiali, esponenziali e trigonometriche con le quali si si può determinare la forma di questo orbitale risolvendo l'equazione di Schrödinger, in quanto si deve fronteggiare un problema a ...
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
approssimato
approssimato [agg. Der. del part. pass. approximatus del lat. approximare "avvicinarsi a", comp. di ad- e proximus "prossimo"] [LSF] Che riguarda o che deriva da un'approssimazione. ◆ [ANM] [...] a.: locuz. con cui s'indicano semplici espressioni polinomiali che, ove si accetti un determinato grado di approssimazione assoluto o quello relativo della f; si ottiene così un'equazione nella quale figurano come incognite gli errori delle misure; se ...
Leggi Tutto