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
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 [...] problema. Un problema è detto NP (che appartiene alla classe NP) se una macchina di Turing non deterministica è in grado di risolverlo in tempopolinomiale. Dati ora due problemi R e Q si dice che «R si riduce a Q» (e si indica con R ∝ Q), se esiste ...
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 [...] interi: nel 1994 Shor ha infatti dimostrato che nel modello di c. quantistico tale problema può essere risolto in tempopolinomiale, risultato che non viene ritenuto possibile in un modello di c. classico. Tale scoperta ha potenzialmente una grande ...
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. Cronologia scientifica: 1961-1970
1961-1970
1961
Famiglia universale. Il giapponese Masatake Kuranishi mostra che esiste sempre un certo tipo di famiglia olomorfa di strutture complesse [...] Negli stessi anni si afferma l'idea che un problema è da considerarsi 'trattabile' se e solo se è risolubile in tempopolinomiale; la classe di tali problemi è indicata con P.
La trasformata veloce di Fourier. Come la classica trasformata di Fourier ...
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
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] che si tratta di un problema NP-completo, nel senso che ogni problema in NP si può ridurre a questo in un tempopolinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma ciò non è stato ancora dimostrato, e anzi costituisce uno dei problemi ...
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 [...] termini di linguaggi. Si introduce quindi un preordine in cui L≤pL′, con L⊂∑ e L′⊂∑′, se esiste una funzione calcolabile in tempopolinomiale f:∑→∑′ con la proprietà
[8] w∈L f(w)∈L′.
Con questa definizione, un linguaggio L si dice NP-completo se L ...
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, [...] di N/4.
Naturalmente il lemma originale specifica l'espressione di Z(N,R), mostrando che il calcolo del predicato può essere eseguito in tempopolinomiale. Si estrae dunque a caso un intero R e si applica il predicato: se risulta Z(N,R)=false, N è ...
Leggi Tutto
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 tempopolinomiale nella dimensione dei dati, e la classe NP come quella di tutti i problemi per cui tale decisione può richiedere ...
Leggi Tutto