Difference between revisions of "Mod q"
m (→Properties) |
m (→Definition) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 2: | Line 2: | ||
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 | 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) \\ | + | :::{| class="wikitable" |
| + | |- | ||
| + | |<math> f(x) = \begin{cases} -1, & if ~ \#\{i \mid x_i = 1\} = 0 & (\mathrm{mod} ~ q) \\ | ||
1 & otherwise \end{cases}</math> | 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>. | 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>. | ||
| Line 10: | Line 13: | ||
==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 == | ||
Latest revision as of 13:39, 20 November 2019
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
