Difference between revisions of "Mod q"
m (→Properties) |
m (→Properties) |
||
| Line 10: | Line 10: | ||
==Properties== | ==Properties== | ||
| − | * Mod q is not in AC<sup>0</sup>: For a given prime <math>p</math>, a depth <math>d</math> circuit which uses only NOT, OR and mod-p gates requires at least <math>\exp O(n^{1/2d})</math> gates in order to compute the function mod-q for any <math>q \neq p^m</math>. <ref>R. Smolensky. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 77-82. DOI=http://dx.doi.org/10.1145/28395.28404 </ref> | + | * Mod q is not in [[Circuit_complexity#AC0 | AC<sup>0</sup>]]: For a given prime <math>p</math>, a depth <math>d</math> circuit which uses only NOT, OR and mod-p gates requires at least <math>\exp O(n^{1/2d})</math> gates in order to compute the function mod-q for any <math>q \neq p^m</math>. <ref>R. Smolensky. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 77-82. DOI=http://dx.doi.org/10.1145/28395.28404 </ref> |
== References == | == References == | ||
Revision as of 08:15, 1 October 2018
Definition
Let [math]q[/math] be a positive integer. The [math]n[/math] variable mod q function is the Boolean function [math]f:\{-1,1\}^n\to\{-1,1\}[/math] defined by
[math] f(x) = \begin{cases} -1, & if ~ \#\{i \mid x_i = 1\} = 0 & (\mathrm{mod} ~ q) \\ 1 & otherwise \end{cases}[/math]
In words, [math]f(x)=-1[/math] if and only if the number of ones in the vector [math]x\in\{-1,1\}^n[/math] is divisible by [math]q[/math].
For [math]q=2[/math], this is the parity function.
Properties
- Mod q is not in AC0: For a given prime [math]p[/math], a depth [math]d[/math] circuit which uses only NOT, OR and mod-p gates requires at least [math]\exp O(n^{1/2d})[/math] gates in order to compute the function mod-q for any [math]q \neq p^m[/math]. [1]
References
- ↑ R. Smolensky. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 77-82. DOI=http://dx.doi.org/10.1145/28395.28404
