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 tempo polinomiale nella dimensione dei dati, e la classe NP come quella di tutti i problemi per cui tale decisione può richiedere tempo ...
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 [...] 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
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
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 [...] la minima lunghezza di un programma che calcola f. Detto Z(f) il numero di radici intere di f, la domanda è se questo sia polinomiale in τ(f) e cioè se esistano costanti A,c tali che per ogni polinomio intero f(t)∈ℤ[t] si abbia
[14] formula.
Il ...
Leggi Tutto
Numeri, teoria dei
Alf van der Poorten
(App. IV, ii, p. 626; V, iii, p. 698; v. aritmetica, IV, p. 370)
La dimostrazione dell'ultimo teorema di Fermat
Le ricerche relative all'ultimo teorema di Fermat, [...] che questa è la soluzione più piccola.
Con equazioni di grado maggiore questo metodo in generale fallisce. Data un'equazione polinomiale a coefficienti interi f(x, y)=0 risulta che ci sono tre casi, apparentemente dipendenti dal grado (totale) di f ...
Leggi Tutto
Numeri, teoria dei
LLarry Joel Goldstein
di Larry Joel Goldstein
SOMMARIO: 1. Introduzione: a) argomenti fondamentali; b) la teoria dei numeri nel XVII e XVIII secolo; c) Gauss. □ 2. Teoria algebrica [...] qualche primo deve ramificarsi in F.
3. Le unità di ℴF. - Sia F=???OUT-Q???(δ) dove δ è una radice dell'equazione polinomiale irriducibile f(x)=0. Supponiamo che f abbia r1 radici reali ed r2 coppie di radici complesse. Allora le unità di ℴF sono ...
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
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 tempo polinomiale, e NP, cui appartengono i problemi che possono essere verificati (ma non risolti) nello stesso modo. In ...
Leggi Tutto