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, [...] polinomiale con una macchina di Turing non deterministica si riducono all'unico problema della soddisfattibilità di espressionibooleane. Negli anni seguenti si riconobbe che numerosissimi problemi ben posti e praticamente rilevanti sono equivalenti ...
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, [...] di tale tipo sono la risolubilità di un sistema di equazioni lineari a variabili intere, la soddisfattibilità di un'espressionebooleana, la possibilità di sequenziare un insieme di lavori su più macchine in modo da rispettare una data scadenza, la ...
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 [...] Kleene, questo insieme di parole si può anche descrivere con un'espressione razionale, e cioè: (ab+b)*(ε+a), dove ε . Un tipico problema della classe PSPAZIO è la soddisfacibilità delle formule booleane con quantificatori, per esempio:
[2] ∀ x ∀ y(x ...
Leggi Tutto