Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the depth of randomly generated circuits

Autor
Tsukiji, T.; Xhafa, F.
Tipus d'activitat
Document cientificotècnic
Data
1996-03-02
Codi
R96-18
Repositori
http://hdl.handle.net/2117/96471 Obrir en finestra nova
Resum
This research is motivated by the Circuit Value Problem; this problem is well known to be inherently sequential. We consider Boolean Circuits with descriptions of length d that consist of gates with a fixed fan-in f and a constant number of inputs. Assuming uniform distribution of descriptions, we show that such a circuit has expected depth O(log d). This improves on the best known result. More precisely, we prove for circuits of size n their depth is asymptotically ef ln n with extremely high p...
Citació
Tsukiji, T., Xhafa, F. "On the depth of randomly generated circuits". 1996.
Paraules clau
Boolean circuits, CVP, Circuit value problem, Coupling technique, NC

Participants

Arxius