1
$\begingroup$

Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$.

Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then do $S_1\cap S_a$. Next go to least element (say $b$) in $S_1\cap S_a$ and do $S_1\cap S_a \cap S_b$)

Finally I want to find the $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-1}}$ where $i_1$ least element in $S_1$ and $i_2$ least element in $S_1\cap S_{i_1}$, $i_3$ least element in $S_1\cap S_{i_1} \cap S_{i_2}$, $\cdots$, $i_{k-1}$ least element in $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-2}}$.

Can we build circuit for this above problem?

What happens if $k$ is fixed? what happens if $k$ is $\log n$?

Can we have logspace algorithm for this problem?

I am familiar with circuits and logics and please help out.

I tried as follows:

first construct a matrix $A$ with $n \times n$ with entries zero's and one's. Find the entry $(i,j)$ is one if $S_i$ have element $j$. other wise zero.

Now we need to find the first non zero entry (say a) in $S_1$ row in $A$ and do or gate $S_1$ row with $S_a$ row in $A$.
Again find the first non zero entry (say b) in $S_1 \vee S_a$ row and do $S_1\vee S_a \vee S_b$.

Now this process I can not able to find the depth and size of circuit. Please let me know what is the circuit size and depth in this process.

$\endgroup$
  • $\begingroup$ I think you should be able to estimate the size and depth of your circuit given what you know. $\endgroup$ – Yuval Filmus May 23 '17 at 14:06
  • $\begingroup$ When you say circuit, what exactly do you mean? Does the circuit have bounded fan-in or unbounded fan-in? What gates are allowed? $\endgroup$ – Yuval Filmus May 23 '17 at 14:06
  • $\begingroup$ think in two cases 1) bounded fan-in 2) unbounded fan-in and gates only and ,or , not gates.... $\endgroup$ – GOLD May 23 '17 at 14:24
  • $\begingroup$ @YuvalFilmus I did not find the depth and size of the following step in above process: "find the first non zero entry (say a) in S_1 row in A and do or gate S_1 row with S_a row in A." $\endgroup$ – GOLD May 23 '17 at 14:25
  • $\begingroup$ I think it is within your capabilities to construct a circuit that computes $S_1 \cap S_a$. Just spend a few hours on it. $\endgroup$ – Yuval Filmus May 23 '17 at 18:23
2
$\begingroup$

You are asking many different questions. The usual rule is one question per post. To help you get started, here is how to compute $S_1 \cap S_{\min S_1}$ (defined as $\emptyset$ if $S_1 = \emptyset$).

The input to the circuit is the $n^2$ variables $x_{i,j}$, indicating $i \in S_j$ (this means that they are TRUE if the condition holds, and FALSE if it doesn't hold). The output to the circuit are $n$ variables $y_i$, indicating whether $i \in S_1 \cap S_{\min A}$.

Let $f_a$ indicate $\min S_1 = a$. Then $$ f_a = \lnot x_{1,1} \land \cdots \land \lnot x_{a-1,1} \land x_a. $$ Given these, we can calculate $$ y_i = x_{i,1} \land \bigvee_{a=1}^n (f_a \land x_{i,a}). $$ We can implement each $f_a$ as a depth 2 circuit with unbounded fan in of size $O(a)$, and each $y_i$ as a depth 2 circuit (with inputs $f_a$ and $x_{i,j}$) with unbounded fan in of size $O(n)$. The circuits for $f_a$ take $O(n^2)$ in total and the circuits for $y_i$ take $O(n^2)$ in total, so altogether we get a depth 4 circuit of size $O(n^2)$.

This circuit is equivalent to a depth $O(\log n)$ circuit of size $O(n^2)$ with bounded fan-in, by replacing each large fan-in gate by a balanced binary tree.

$\endgroup$
  • $\begingroup$ Thanks and your answer helped me a lot. Is this total circuit for $S_1\cap S_{i_1} \cap S_{i_2}⋯\cap S_{i_k}$ has $4k$ depth and size $O(kn^2)$ ? If $k$ is fixed then circuit is in $AC_0$. If $k$ is at most $\log n$ then circuit is in $NC_1$. Am i right? $\endgroup$ – GOLD May 24 '17 at 9:57
  • $\begingroup$ If $k$ is at most $\log n$ then the circuit is in $\mathsf{AC}^1 \subseteq \mathsf{NC}^2$. $\endgroup$ – Yuval Filmus May 24 '17 at 10:19
  • $\begingroup$ Can we make circuit which is in $NC^1$ if $k$ is at most $\log n$? $\endgroup$ – GOLD May 25 '17 at 10:22
  • $\begingroup$ Perhaps we can, perhaps we can't. $\endgroup$ – Yuval Filmus May 25 '17 at 20:20
  • $\begingroup$ Can we show this problem is in $NL$-complete? if $k$ is at most $\log n$. I tried this problem is $NL$ or $NC^1$ but i did not. $\endgroup$ – GOLD Jun 1 '17 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.