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
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, [...] appartiene a S, esiste una dimostrazione di questo fatto (codificata in una sequenza binaria) che può essere verificata, in tempopolinomiale, da un algoritmo che ne esamina solo un numero prefissato di bit, scelti a caso.
L'introduzione di elementi ...
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
Computer science
Scott Kirkpatrick
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e l’ingegneria, costituendo dal punto di vista accademico un settore [...] unità parallela verifichi una possibile dimostrazione della risposta, può risolvere il problema decisionale in un tempopolinomiale. Sfortunatamente, il numero di unità parallele richieste per la verifica della risposta cresce almeno esponenzialmente ...
Leggi Tutto
La grande scienza. Computer science
Scott Kirkpatrick
Computer science
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e dell'ingegneria, costituendo dal [...] unità parallela verifichi una possibile dimostrazione della risposta, può risolvere il problema decisionale in un tempopolinomiale. Sfortunatamente, il numero di unità parallele richieste per la verifica della risposta cresce almeno esponenzialmente ...
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
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 tempopolinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma ciò non è stato ancora dimostrato e anzi costituisce uno dei problemi ...
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
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] se i calcolatori quantistici siano reralmente più potenti di quelli classici. Se chiamiamo QP la classe dei problemi risolubili in tempopolinomiale con macchine quantistiche il fatto che l'inclusione di P in QP sia o meno stretta è uno dei tanti ...
Leggi Tutto
problemi NP-completi
Mauro Cappelli
I problemi di decisione possono essere classificati prescindendo dall’algoritmo usato per risolverli. Sono state individuate le classi di problemi P, NP e NP-completi. [...] Infatti, se un problema R è nella classe NP-completa, allora per definizione tutti i problemi in NP possono essere ridotti in tempopolinomiale a R; ma se R∈P, allora ciò proverebbe che P =NP in contrasto con la congettura. Ci si può chiedere allora ...
Leggi Tutto