The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] parallel complexity classes(1hit)

1-1hit
  • On Depth-Bounded Planar Circuits

    Masao IKEKAWA  

     
    PAPER

      Vol:
    E75-D No:1
      Page(s):
    110-115

    We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.