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, [...] , memoria, ecc.) sono necessarie per tale calcolo. Una classe di problemi si dice calcolabile in tempopolinomiale, o in P, se ognuno di essi è risolvibile in un numero di passi maggiorato da un polinomio nelle dimensioni dell’input. Una classe è ...
Leggi Tutto
Selezione di 7 problemi matematici proposti nel 2000 dal Clay Mathematics Institute (CMI) di Cambridge, Massachusetts, che ha stanziato per la risoluzione di ognuno di essi un premio di 1 milione di dollari. [...] di complessità computazionale P, cui appartengono i problemi che possono essere risolti con un algoritmo deterministico in un tempopolinomiale, e NP, cui appartengono i problemi che possono essere verificati (ma non risolti) nello stesso modo. In ...
Leggi Tutto
La grande scienza. Combinatoria
Peter J. Cameron
Combinatoria
Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri essa non rappresenta una branca separata, [...] : si dimostra che un certo numero di problemi di teoria dei grafi appartengono alla classe P dei problemi risolvibili in tempopolinomiale (ma la dimostrazione non è costruttiva, per cui nella maggior parte dei casi non viene fornito alcun algoritmo ...
Leggi Tutto
Finito
Antonio Machì
(XV, p. 399)
Matematica del finito
Diversi filoni della ricerca matematica che mostrano particolare vitalità si possono ricondurre all'interesse per i problemi del finito. L'analisi [...] nello studio delle permutazioni delle radici di una certa equazione polinomiale.Lo studio di strutture finite e dei loro gruppi di enunciò senza dimostrazione. Si tratta sempre, nelle ricerche del tempo di Galois, e per un certo periodo anche in ...
Leggi Tutto
La civilta islamica: antiche e nuove tradizioni in matematica. L'algebra e il suo ruolo unificante
Roshdi Rashed
L'algebra e il suo ruolo unificante
La seconda metà del VII sec. vede il costituirsi [...] di al-ḫalīl riflette un ulteriore aspetto dello scenario intellettuale del tempo: non vi sono compartimenti stagni tra arte e scienza, di Ruffini-Horner, che egli applica alle equazioni polinomiali e non più soltanto all'estrazione della radice di ...
Leggi Tutto
L'Ottocento: matematica. Le origini della teoria dei gruppi
Jeremy Gray
Le origini della teoria dei gruppi
La teoria di Galois e la soluzione algebrica delle equazioni algebriche
La teoria di Galois [...] che ci condurrebbero troppo lontano), Jacobi trova un'equazione polinomiale di grado 5 che si può ridurre con manipolazioni di quest'ultimo su tale argomento si estendono attraverso un arco di tempo che va dal 1913 al 1916, le importanti novità che ha ...
Leggi Tutto
L'Ottocento: matematica. Teoria dei numeri
Catherine Goldstein
Teoria dei numeri
Le tappe più significative dello sviluppo di un settore della scienza o dell'arte si accordano raramente con la suddivisione [...] teoria dei numeri ha raggiunto l'età matura solo negli ultimi tempi" (Hilbert 1897 [1932-35, I, p. 65]).
Innanzitutto una variabile, ossia delle funzioni f(z) che soddisfano un'equazione polinomiale P(z,f(z))=0, basandosi su alcune analogie tra queste ...
Leggi Tutto
Numeri
Umberto Zannier
Quanti? Quanto? Quando? A che distanza? Domande a cui rispondiamo, di solito, con numeri. Di essi facciamo continuo uso, e l’importanza concettuale, oltre che pratica, della nozione [...] essere considerata sicura.
Il problema di fattorizzare numeri in tempi rapidi è molto interessante e, come si è detto, importante. Non soltanto non si conosce un metodo generale con complessità polinomiale, ma non si sa nemmeno se possa esistere. Si ...
Leggi Tutto