ON THE COMPLEXITY OF PLANAR BOOLEAN CIRCUITS

Authors
TURAN G
Citation
G. Turan, ON THE COMPLEXITY OF PLANAR BOOLEAN CIRCUITS, Computational complexity, 5(1), 1995, pp. 24-42
Citations number
30
Categorie Soggetti
Mathematics, General","Computer Sciences",Mathematics,"Computer Science Theory & Methods
Journal title
Computational complexity → ACNP
ISSN journal
10163328
Volume
5
Issue
1
Year of publication
1995
Pages
24 - 42
Database
ISI
SICI code
1016-3328(1995)5:1<24:OTCOPB>2.0.ZU;2-F
Abstract
We consider planar circuits, formulas and multilective planar circuits . It is shown that planar circuits and formulas are incomparable. An O mega(n log n) lower bound is given for the multilective planar circuit complexity of a decision problem and an Omega(n(3/2)) lower bound is given for the multilective planar circuit complexity of a multiple out put function.