18

The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, \dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $...


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 ...


3

The trick is, unlike classical gates, quantum gates have to be reversible (aka invertible). In other words, for every possible output, there must be one and only one possible input producing that output. This means the classical NAND gate can't possibly work in quantum computing: there are more inputs than outputs, so by the pigeonhole principle there must ...


3

The NAND gate is not reversible, you can't recover its inputs using its outputs, so it's not a well defined quantum gate. Or, at the very least, it must contain some sort of internal measurement mechanism that would cause decoherence. This would prevent it from being universal for quantum computation. A simple way to fix the reversibility problem is to have ...


3

This is impossible, a shift does not combine two operands.


3

In the zeroth order sense, it is correct that the logic depth and the time to execute the logic would be the same. There are nuances to this because you need to do something with the result. What logic is a medium to do work. In the simplest sense, you have a bounded function with inputs and outputs: In most actual systems, you need a way to hold the ...


2

Unrestricted Boolean circuits are not very interesting, since they can compute any function. The class of Boolean functions they compute is the class of all Boolean functions. In order to make Boolean circuits more interesting, we need to put restrictions on them. The following seem to be the most common restrictions: Upper bounds on the size. Upper bounds ...


2

The automaton as represented by a combinational logic circuit (CLC) is called combinational logic. Its model of computation is given an input, a CLC is used to compute the output. The name of that model of computation can also be called combinational logic. (This is similar to Turing machine, which is a kind of computing machine and also the name of the ...


2

Whenever you are faced with two Boolean expressions $f,g$ on $n$ variables and wish to know whether they are equivalent, there is a simple algorithm you can apply: Go over all $2^n$ possible truth assignments, and check whether $f$ and $g$ have the same truth value on each. While this is infeasible for large $n$, in your case $n = 4$, so there are only ...


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

With such an instruction set, all you could express are straight-line programs. Without branches, you can't have loops. Thus, the program would not be able to handle arbitrary-length inputs: it would be limited to dealing with fixed-size inputs (or inputs with a fixed known upper bound on the size of the input). So, that wouldn't be very satisfactory.


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 ...


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 ...


1

The NAND gate is "universal" in that a network of NAND gates can implement any combinational or sequential logic function. So to construct a "program" out of NANDs all you need is a way of specifying the network that interconnects them. So if every NAND gate in your "computer" has a address, and the list of instructions is of the form inputA,inputB you ...


1

Unfortunately, you've gotten as far as you can get on this problem. (Note: I'm going to write AND, OR, NOT, and NAND as $\wedge \vee \neg \uparrow$ respectively, since the standard sum/product/overbar notation tends to end up with lots of stacked bars, and I don't like those.) You currently have: $$(a \wedge \neg b) \vee (\neg a \wedge b) \vee (a \wedge b)...


1

Some further thoughts, at least for the case when batch generation is done by feeding a gray code or other simply generated sequence into a circuit with internal memory. For an ordinary combinatorial logic circuit without memory, we can bound the size of a circuit needed to evaluate a general function on n bits in two ways: by providing a general ...


1

You can think of Turing machines as a finite description of a function whose domain is $\mathbb{N}$. When you want to specify a different behavior for each member in a collection of finite sets which covers the entire domain, Turing machines are not the natural object to discuss. You could obviously talk about a sequence of machines $M_n$, where $M_i$ ...


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