# Tag Info

5

If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}[O(n^k)]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and ...

4

Usually $+$ means $\lor$, "multiplication" means $\land$, and $'$ means $\lnot$.

3

Let $1000 \leq s \leq 2^n/n$. Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$. Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on ...

2

The Cook–Levin theorem shows how to construct a circuit of size $f(n)^{O(1)}$. I'm not sure what's the best exponent. The opposite direction is impossible, since circuits of size 1 can compute the following language: $$\{ w : \text{the |w|th Turing machine halts on the empty input} \}.$$ More generally, circuits of size 1 can compute any language ...

2

OK so now I figured this out. The problem is $NP$-complete. We could simply verify an assignment by checking each gate as an equation. For solving SAT of boolean function A(x), simply construct a equation, $y=y\otimes\lnot A(x)$ would suffice.

2

In an $\mathsf{NC^0}$ circuit, every output bit depends on a bounded number of input bits. But the $k$th bit of the output (counting from the LSB) depends on the first $k$th bits of each input. To see that $\mathsf{AC^0}$ circuits can compute addition, we need to produce such a circuit. Hopefully you have seen such circuits, and otherwise perhaps you can ...

2

Multiplication can be done even with stronger restrictions, like $AC^1$ with bounded fan-in. Proof is little hard to typeset here, but I will outline the sketch and give a link. You shall prove, that addition of two m-bit numbers have $O(m)$ size and constant depth circuit and thus is in $AC^0$. This is pretty simple (start with looking for $O(m)$ depth ...

2

This is a NOR gate. You can implement a NOR gate using a combination of a OR and a NOT gate. However, in MOSFET implementation or other technologies (i.e. electrical hardware architecture), we can build a NOR gate directly and more efficiently (i.e. more efficient than using a OR and a NOT gate). That's why we use NOR as well.

1

Yes, that's correct. See the Tseitin transform, which describes how. It doesn't matter how the circuit $C$ was constructed.

1

What's wrong with A AND (NOT B)?

1

What you describe is essentially Turing machines with advice, the advice for length $i$ being simply the description of $T_i$. It is a classic result that the two models are equivalent in the case of poly-time TMs and poly-sized circuits, that is, both produce the same class $\mathsf{P}/\mathrm{poly}$. If the description length of $T_i$ is allowed to be ...

1

Morioka considers uniform versions of his circuit classes: Throughout this paper we write $\mathbf{NC^1}$ to mean $\mathbf{Dlogtime}$-uniform $\mathbf{NC^1}$, which is equivalent to the class $\mathbf{Alogtime}$ of languages accepted by an alternating Turing machine in $O(\log n)$ time. The paper you mention should imply the equivalence of these two ...

1

an $NC^0$ can only consider circuits of fan-in 2. If we try to adding with a Full-Adder with Lookahead Gatter to calculate the carry, needs every Full-Adder 3 Input signals. But in $NC^0$ are only 2 inputs allowed. If we try to replace Full-Adder with other logic gatters, we hurt the depth of the circuit. image-source: https://upload.wikimedia.org/...

1

The Boolean circuits you are referring to are a non-uniform model. This means that, for every input length, you have a different circuit. When we say that Boolean circuits solve a particular problem what is actually meant is that a family of circuits does, which is an infinite sequence $(C_n)_{n \in \mathbb{N}_0}$, $C_n$ being the circuit for inputs of ...

Only top voted, non community-wiki answers of a minimum length are eligible