In complexity theory, The size of a linear circuit is given by the number of its nodes. What do we mean when we say superlinear size? and What do we mean when we say Nonlinear lower bounds?
Asked
Active
Viewed 54 times
0
-
1The bounds apply to parameterized families of circuits. – Fabio Somenzi Dec 22 '16 at 17:56
-
Can you give me an example please – Mehrema Dec 22 '16 at 18:02
-
1A classic example is the family of circuits that compute the parity of $n$ bits. You can build circuits to compute the parity of $n$ bits that have $O(n)$ nodes. – Fabio Somenzi Dec 22 '16 at 18:17