# Tag Info

105

Addition is fast because CPU designers have put in the circuitry needed to make it fast. It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers have judged it to be worth it. See https://en.wikipedia.org/wiki/Adder_(electronics). Both can be made fast enough to execute within a single CPU cycle. They'...

38

There are several aspects. The relative cost of a bitwise operation and an addition. A naive adder will have a gate-depth which depend linearly of the width of the word. There are alternative approaches, more costly in terms of gates, which reduce the depth (IIRC the depth then depend logarithmically of the width of the word). Others have given ...

24

CPUs operate in cycles. At each cycle, something happens. Usually, an instruction takes more cycles to execute, but multiple instructions are executed at the same time, in different states. For example, a simple processor might have 3 steps for each instruction: fetch, execute and store. At any time, 3 instructions are being processed: one is being fetched, ...

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 $... 14 Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function$f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate polynomial$p(x_1,\dots,x_n)$such that$f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$for all$x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field$\...

13

Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$). To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $\... 12 Processors are clocked, so even if some instructions can clearly be done faster than others, they may well take the same number of cycles. You'll probably find that the circuitry required to transport data between registers and execution units is significantly more complicated than the adders. Note that the simple MOV (register to register) instruction ... 12 Addition is important enough to not have it wait for a carry bit to ripple through a 64-bit accumulator: the term for that is a carry-lookahead adder and they are basically part of 8-bit CPUs (and their ALUs) and upwards. Indeed, modern processors tend to need not much more execution time for a full multiplication either: carry-lookahead is actually a ... 11 Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field$\mathbb{F}$with$n$variables and total degree$d$can compute functions$f:\mathbb{F}^n\rightarrow\mathbb{F}$of the form: $$f(x_1,...,x_n)=\sum\limits_{i_1+...+i_n\le d}\alpha _{i_1,...,i_n}\cdot x_1^{i_1}x_2^{i_2}...x_n^{i_n}$$ where$\alpha _{i_1,...,i_n}\...

10

From the wikipedia article that you cited: The Toffoli gate is universal; this means that for any boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits (called garbage). Essentially, this ...

9

Languages in $AC^0$ can be more complicated than naive intuition might suggest. Obviously, $AC^0$ contains $\{a^n b^n c^n\}$, which is non-context-free. Every unary language is in nonuniform $AC^0$; for example, the halting problem expressed in unary. Addition can be implemented in $AC^0$ with a carry-lookahead adder. Here the input is $2n$ bits ...

9

The Boolean AND function can not be computed. Suppose actually that the AND function is computed by an $\text{OR} \circ \text{MOD}$ circuit. Then it follows that one of the MOD subcircuits must compute then AND function already, which is impossible.

9

Logic circuits are common in complexity theory, where they go by the name circuits. There is a big difference between circuits and models of computation such as the Turing machine: each circuit can only handle inputs of fixed size. In order to fix this, under the circuit computation model, for every input length $n$ there is a circuit $C_n$, and together ...

9

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. ...

9

I think you'd be hard pressed to find a processor that had addition taking more cycles than a bitwise operation. Partly because most processors must carry out at least one addition per instruction cycle simply to increment the program counter. Mere bitwise operations aren't all that useful. (Instruction cycle, not clock cycle - e.g. the 6502 takes a minimum ...

8

From S. Chaudhuri, J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity: Theorem 6.1: A circuit computing $T_k^n$ with $k \leq n^{1/3}$ has $\Omega(k^2(\ln n)/\ln k)$ gates Where $T_k^n$ is the boolean function that has the value 1 iff at least $k$ of its inputs have the value 1 (threshold function).

8

Take a language $L$ which is not in $\mathsf{E} = \bigcup_{c=1}^\infty \mathsf{TIME}(2^{cn})$. Now consider the language $L' = \{1^m : m \in L\}$. Then $L'$ is clearly in $\mathsf{P/poly}$, but it's not in $\mathsf{P}$: if it were decidable in time $O(m^k)$, then we could decide $L$ in time $O((2^n)^k)$, and so $L$ would be in $\mathsf{E}$. Our decision ...

8

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.

8

At the gate level, you are correct that it takes more work to do addition, and thus takes longer. However, that cost is sufficiently trivial that doesn't matter. Modern processors are clocked. You cannot do instructions at anything except multiples of this clock rate. If the clock rates were pushed higher, to maximize the speed of the bitwise operations, ...

7

A flip-flop is implemented as a bi-stable multivibrator; therefore, Q and Q' are guaranteed to be the inverse of each other except for when S=1, R=1, which is not allowed. The excitation table for the SR flip-flop is helpful in understanding what occurs when signals are applied to the inputs. S R Q(t) Q(t+1) ---------------- 0 x 0 0 1 0 ...

7

The (very) simplified version is that they convert any verification algorithm $A$ for a language $L \in \text{NP}$ into a circuit. What they end up with is a circuit $C$ that, given a (binary) string $x$ is satisfiable (i.e. $C(x)=1$) if and only if $x \in L$ (i.e. there exists a certificate $y$ such that $A(x,y) = 1$). They do this by encoding the working ...

7

I guess it depends on your point of view, but the proof via approximating polynomials (along the lines of Razborov-Smolensky) that Parity isn't in AC0 is not so involved... The natural way in which one would modify the proof that "NEXP is not in ACC0" to yield "NEXP not in AC0" would be to give a SAT algorithm for AC0 circuits that beats exhaustive search. ...

7

This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see ...

7

For a univariate polynomial $p(x)$, yes, it's that easy. For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works. In particular, when you write "a polynomial of degree $d$ has at most $d$ roots", that is true for univariate polynomials $p(x)$, but it is not true in general for multivariate polynomials. Ricky Demer gives a simple ...

7

Modern processors are clocked: Every operation takes some integral number of clock cycles. The designers of the processor determine the length of a clock cycle. There are two considerations there: One, the speed of the hardware, for example measured as the delay of a single NAND-gate. This depends on the technology used, and on tradeoffs like speed vs. power ...

7

There are only so many circuits using at most $m$ gates, say $f(m)$. If all Boolean functions on $n$ inputs could be computed using at most $m$ gates, then $f(m) \geq 2^{2^n}$, since there are $2^{2^n}$ Boolean functions on $n$ inputs. Hence if $f(m) < 2^{2^n}$ then there must be a function on $n$ inputs which cannot be computed using at most $m$ gates. ...

6

No. Take for example $\mathsf{AC^0}$. It is polynomial-size bounded-depth circuits. Being DAG or tree doesn't change the class. The fan-in can be arbitrarily large. If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with ...

6

Given $w_1,\ldots,w_n,t$, let $X$ be the set of assignments such that $\sum_i w_i x_i \geq t$, and consider the linear program with variables $z_1,\ldots,z_n$ and the $2^n$ constraints \begin{align*} \sum_i z_i x_i \geq +1 & (x_1,\ldots,x_n) \in X \\ \sum_i z_i x_i \leq -1 & (x_1,\ldots,x_n) \notin X \end{align*} This linear program (with a ...

6

Straight-line programs and arithmetic circuits are two equivalent ways of describing the same computational model. A straight-line program typically has the following instructions: Reading the input: $t_i \gets x_j$. Initialization by constants: $t_i \gets r$ for all $r$ in the ambient field. Addition, subtraction, multiplication, division: $t_t \gets t_j \... 6$\mathsf{P/Poly} = \bigcup\limits_{k\in\mathbb{N}}\mathsf{SIZE}(n^k)$. We don't know if every language in$\Sigma_2$has a polynomial size circuit, but we do know that we cannot have polynomial circuits of bounded degree,i.e.$\mathsf{SIZE}(n^k)$for some$k\in \mathbb{N}$, for all languages in$\Sigma_2\$ (Kannan's theorem).

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