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 [...] Karp-riducibile in tempo polinomale a un problema di decisione B se dato un caso x del problema A è possibile creare (in tempo polinomiale) un caso f(x) del problema B tale che x ha soluzione positiva se e solo se f(x) ha soluzione positiva. In base ...
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, [...] ∈L1 se e solo se f(v)∈L2. Si dice allora che 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 algoritmo A2 per risolvere P2 può essere usato per risolvere P1 ...
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. [...] contiene. Dati ora due problemi R e Q, si dice che R si riduce a 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 tale che la soluzione dell’istanza di Q fornisce la soluzione della ...
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, [...] un numero composto o è un numero primo (test di primalità), un problema per il quale non è, ancora oggi, noto alcun algoritmo polinomiale.
Definiamo certificato di non primalità di un intero n un altro intero m, con 1〈m〈n, dotato di proprietà tali da ...
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, [...] problema X si dice completo per una classe C se ogni problema appartenente a C si può trasformare in X con complessità polinomiale. In altri termini, nessun problema in C è 'più difficile' di X. Se esiste un algoritrno che risolve X con complessità O ...
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 [...] . Dati ora due problemi R e Q si dice che «R si riduce a 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 tale che la soluzione dell’istanza di Q fornisce la soluzione della ...
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 tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma ciò non è stato ancora dimostrato e anzi costituisce uno dei problemi ...
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 tempo polinomiale. Ovviamente P⊂NP; è ragionevole supporre che P≠NP, ma ciò non è stato ancora dimostrato, e anzi costituisce uno dei problemi ...
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 [...] decisionale ci si propone di verificare una soluzione proposta, lo si può fare in un tempo che è funzione polinomiale (e non esponenziale) di n. Dunque un ipotetico computer ad architettura altamente parallela, in cui ogni unità parallela verifichi ...
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 [...] decisionale ci si propone di verificare una soluzione proposta, lo si può fare in un tempo che è funzione polinomiale (e non esponenziale) di n. Dunque un ipotetico computer ad architettura altamente parallela, in cui ogni unità parallela verifichi ...
Leggi Tutto