Funzioni simmetriche

[bh3u4m]

Esiste un trucchetto carino per ridurre la funzione f(x, y, n) = x[sup]n[/sup]+y[sup]n[/sup] in espressione composta da $ \\ \sigma_1 = x+y \\ \sigma_2 = x \cdot y \\ f(x, y, 0) = 2 \\ $usando la seguente regola:
$ f(x, y, n) = \sigma_1 \cdot f(x, y, n-1) + \sigma_2 \cdot f(x, y, n-2) $

Un programma che usa detta regola ha natura esponenziale ed è perciò troppo lento, trovare una soluzione migliore (non sono sicuro che esista).

[CUCU]

Esiste un trucchetto carino per ridurre la funzione f(x, y, n) = x[sup]n[/sup]+y[sup]n[/sup] in espressione composta da $ \\ \sigma_1 = x+y \\ \sigma_2 = x \cdot y \\ f(x, y, 0) = 2 \\ $usando la seguente regola:
$ f(x, y, n) = \sigma_1 \cdot f(x, y, n-1) + \sigma_2 \cdot f(x, y, n-2) $

Un programma che usa detta regola ha natura esponenziale ed è perciò troppo lento, trovare una soluzione migliore (non sono sicuro che esista).

hai commesso degli errori di digitazione.
intendi la funzione x^n+y^n?
in tal caso è ovvio che non possono esistere algoritmi di tempo polinomiale per calcolarla dove il tempo è misurato in funzione della lunghezza dell'input in bit.
Infatti esistono input di lunghezza n (dove n è la lunghezza delle codifiche di x,y,n) che producono output di lunghezza Omega(2^n), e il numero di passi di esecuzione di un calcolatore seriale è sempre maggiore o uguale allo spazio impiegato (serve almeno una unità di tempo per scrivere ogni singolo bit dell'output).

Però sotto l'ipotesi che gli input siano di lunghezza fissa e le operazioni aritmetiche impieghino tempo costante, e che quindi il tempo d'esecuzione dipenda da x,y e n, allora esiste un semplice algoritmo polinomiale per calcolarla (in particolare il cui tempo dipende solo da n):

consideriamo la funzione
int exp(x,n)
{
int i=x;
int out=1;
int j=1;
int k=1;
while(j<=n)
{
if (k-esimo bit di n è uguale ad 1) out=out*i;
i=i*i;
j=j*2;
k=k+1;
}
return out;
}

Allora la nostra funzione è f(x,y,n)=exp(x,n)+exp(y,n)
che quindi ha tempo d'esecuzione Theta(log(n)).