An exact characterization of symmetric functions in \(qAC^{0}[2]\) (Q5941440): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:49, 30 January 2024
scientific article; zbMATH DE number 1635633
Language | Label | Description | Also known as |
---|---|---|---|
English | An exact characterization of symmetric functions in \(qAC^{0}[2]\) |
scientific article; zbMATH DE number 1635633 |
Statements
An exact characterization of symmetric functions in \(qAC^{0}[2]\) (English)
0 references
20 August 2001
0 references
\(qAC^{0}[2]\) is the class of languages computable by circuits of constant depth and quasi-polynomial \((2^{\log^{O(1)}n})\) size with unbounded fan-in AND, OR, and PARITY gates. Symmetric functions are those functions that are invariant under permutations of the input variables. Thus, a symmetric function \(f_{n}: {0,1}^{n}\rightarrow{0,1}\) can also be seen as a function \(f_{n}: {0,1,\ldots,n}\rightarrow{0,1}\). We give the following characterization of symmetric functions in \(qAC^{0}[2],\) according to how \(f_{n}(x)\) changes as \(x\) grows from \(0\) to \(n.\) A symmetric function \(f=(f_{n})_{n\in N}\) is in \(qAC^{0}[2]\) if and only if \(f_{n}\) has period \(2^{t(n)}=\log^{O(1)}n\) except within both ends of length \(\log^{O(1)}n\).
0 references
circuit complexity
0 references
lower bound
0 references
symmetric function
0 references
period
0 references
parity function
0 references