litow@uwm-cs.UUCP (Dr. B. Litow) (01/14/87)
I would like to suggest in a tentative way that A^(2/3) represents a kind of physical upper bound on NC circuit size. NC is well represented by planar technologies and A^(2/3) where A is Avogadro's Number gives,roughly, the number of molecular dimension gates possible in a small 'plane' of 'ordinary' matter. This value is about 2^52.7 which accords nicely with cubic and quartic degree circuit families. In the cubic case one gets data size of 2^16 bits on input and for the quartic 2^12 bits. A good reference to NC is "On Uniform Circuit Complexity" by W.Ruzzo,JCSS 1981,365-383.A fairly recent look at NC is "A Taxonomy of Problems with Fast Parallel Algorithms" in Inf. & Cont.,1985,2-22. Clearly this value A^(2/3) is very likely going to require a new method of physically realizing boolean gates on the molecular level with dissipation in the range < 100kT (anyway a few tens of eV). ?