fbcyborg
21-02-2010, 18:06
Salve gente,
sono giorni che non riesco a trovare una soluzione convincente a questo problema:
Sapendo che la somma e il prodotto di n bit si possono effettuare con circuiti di profondità log n, a che classe appartiene il problema di decidere, dati due vettori di m interi, ciascuno di n bit, se il loro prodotto scalare è uguale a un intero dato k?
Di primo impatto direi che serve un circuito con profondità 3 log n, ma facendo dei ragionamenti che non vorrei ancora pronunciare mi torna log n * log n.
Quindi secondo la prima ipotesi sarebbe NC1.
Qualcuno mi da una mano per favore?
sono giorni che non riesco a trovare una soluzione convincente a questo problema:
Sapendo che la somma e il prodotto di n bit si possono effettuare con circuiti di profondità log n, a che classe appartiene il problema di decidere, dati due vettori di m interi, ciascuno di n bit, se il loro prodotto scalare è uguale a un intero dato k?
Di primo impatto direi che serve un circuito con profondità 3 log n, ma facendo dei ragionamenti che non vorrei ancora pronunciare mi torna log n * log n.
Quindi secondo la prima ipotesi sarebbe NC1.
Qualcuno mi da una mano per favore?