patternMinor
Computing MOD_4 function using MOD_2, OR, AND, NOT gates
Viewed 0 times
mod_2functiongatesusingmod_4andnotcomputing
Problem
Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows:
Let $x_1,\cdots,x_n$ be the input. Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $x_1,\dots,x_n$ is divisible by $q$; $\MOD_q(x_1,\cdots,x_n)=1$ otherwise.
I want to compute $\MOD_4$ using a constant depth circuit using only the following gates: $\MOD_2$ gates and the usual AND, OR, NOT gates. Gate fan-in is unbounded. Technically I want to show that $\MOD_4 \in \text{ACC}_0[2]$, where $\text{ACC}_0[2]$ means alternating circuit of constant depth with parity gates ($\MOD_2$ counters). Or more generally, I want to show that $\MOD_{p^k} \in \text{ACC}_0[p]$.
Can this be done? Is there a way to compute $\MOD_4$ using $\MOD_2$, AND, OR, and NOT gates?
My attempt: If I pass the input through a $\MOD_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD_4$ is also $= 1$. But $\MOD_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.
Let $x_1,\cdots,x_n$ be the input. Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $x_1,\dots,x_n$ is divisible by $q$; $\MOD_q(x_1,\cdots,x_n)=1$ otherwise.
I want to compute $\MOD_4$ using a constant depth circuit using only the following gates: $\MOD_2$ gates and the usual AND, OR, NOT gates. Gate fan-in is unbounded. Technically I want to show that $\MOD_4 \in \text{ACC}_0[2]$, where $\text{ACC}_0[2]$ means alternating circuit of constant depth with parity gates ($\MOD_2$ counters). Or more generally, I want to show that $\MOD_{p^k} \in \text{ACC}_0[p]$.
Can this be done? Is there a way to compute $\MOD_4$ using $\MOD_2$, AND, OR, and NOT gates?
My attempt: If I pass the input through a $\MOD_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD_4$ is also $= 1$. But $\MOD_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.
Solution
Suppose for simplicity that the number of ones in the input is even, and we want to know whether it is divisible by 4 or not. Intuitively, what we would like to do is to somehow "halve" the number of ones in the input; then divisible by 4 would correspond to even, and not divisible by 4 would correspond to odd. Since we have parity gates in our disposal, we would be able to solve our problem.
How do we "halve" the number of ones? The idea is to consider the running sums
$$ y_i = x_1 \oplus \cdots \oplus x_i. $$
Each time $x_i = 1$, we have $y_{i+1} \neq y_i$. Half the time, $y_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.
How do we "halve" the number of ones? The idea is to consider the running sums
$$ y_i = x_1 \oplus \cdots \oplus x_i. $$
Each time $x_i = 1$, we have $y_{i+1} \neq y_i$. Half the time, $y_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.
Context
StackExchange Computer Science Q#56343, answer score: 3
Revisions (0)
No revisions yet.