Skip to main content
Share Your Experience: Take the 2024 Developer Survey
110 votes
Accepted

Why is addition as fast as bit-wise operations in modern processors?

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 ...
D.W.'s user avatar
  • 160k
43 votes

Why is addition as fast as bit-wise operations in modern processors?

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 ...
AProgrammer's user avatar
  • 3,069
26 votes

Why is addition as fast as bit-wise operations in modern processors?

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 ...
Paul92's user avatar
  • 528
25 votes
Accepted

Why aren't P and P/poly trivially the same?

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$ ...
David Richerby's user avatar
15 votes

Does there exist an equivalent arithmetic circuit for each computable function?

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 ...
D.W.'s user avatar
  • 160k
13 votes

Why is addition as fast as bit-wise operations in modern processors?

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 ...
James Hollis's user avatar
13 votes
Accepted

Representing binary functions with a finite gate set without exponential blow-up?

No. No matter what representation of functions as circuits/formulas you use, there will exist some functions that require exponential size to represent. This was proven by Shannon in 1949. See ...
D.W.'s user avatar
  • 160k
12 votes

Why is addition as fast as bit-wise operations in modern processors?

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 ...
user72735's user avatar
  • 121
10 votes
Accepted

Does there exist an equivalent arithmetic circuit for each computable function?

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\...
Ariel's user avatar
  • 13.4k
10 votes

Why is addition as fast as bit-wise operations in modern processors?

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 ...
pjc50's user avatar
  • 411
10 votes
Accepted

How to show that hard-to-compute Boolean functions exist?

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}...
Yuval Filmus's user avatar
9 votes

Why is addition as fast as bit-wise operations in modern processors?

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 ...
Cort Ammon's user avatar
  • 3,351
8 votes
Accepted

Is Green's the best 16-input sorting network so far?

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 ...
David Richerby's user avatar
8 votes

Why is addition as fast as bit-wise operations in modern processors?

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,...
gnasher729's user avatar
  • 30.4k
8 votes
Accepted

What does "AC0 many-one reduction" mean?

An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping ...
D.W.'s user avatar
  • 160k
7 votes

What does "AC0 many-one reduction" mean?

The "what is" part of the question was succinctly answered by D.W.: An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time ...
Thomas Klimpel's user avatar
6 votes

On relation between FFT and polynomial multiplication

Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries. $$M = |u\rangle\langle v| = \begin{bmatrix} u_0 v_0 & u_1 v_0 & u_2 v_0 & \dots & ...
Craig Gidney's user avatar
  • 5,862
6 votes

Is Green's the best 16-input sorting network so far?

The lower bound for an problem states that "no algorithm can do better than this". In your case, it means that no sorting network for 16 inputs can have fewer than 53 gates. Sometimes there can be ...
Nayuki's user avatar
  • 881
6 votes
Accepted

Why do all recent SAT solvers work on CNF instead of circuit SAT?

there are a lot of different angles on your question. generally agreed with your premise that looking at "structural information" in a SAT formulation ought to be an excellent research area. SAT ...
vzn's user avatar
  • 11k
6 votes

Why is addition as fast as bit-wise operations in modern processors?

Let me correct a few things that were not mentioned that explicitely in your existing answers: I know that bitwise operations are so fast on modern processors, because they can operate on 32 or 64 ...
AnoE's user avatar
  • 1,273
6 votes

Show that boring boolean circuit belongs to NP-complete class

The problem is PP-hard. This means that unless the polynomial hierarchy collapses to NP, then deciding whether a circuit is boring is not in NP (and consequently is not NP-complete). The collapse ...
Ariel's user avatar
  • 13.4k
5 votes
Accepted

Lower bound of degree of polynomial approximating parity

You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$). ...
jschnei's user avatar
  • 379
5 votes
Accepted

How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

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 $\...
Robert Andrews's user avatar
4 votes

Is it possible to determine if C=A+B faster than adding A+B in logical circuits

Consider computing $\overline{a_{n-1}\ldots a_0}+\overline{b_{n-1}\ldots b_0}=\overline{c_{n-1}\ldots c_0}$. If the last $(k+1)$-bits are correctly computed, then $c_{k+1}$ is correct if and only if $$...
Wei Zhan's user avatar
  • 1,183
4 votes
Accepted

Regular Languages in $ \mathsf{\text{}NC^1}$

Let $L$ be a regular language. Take some DFA $\langle q_0, Q, \delta, F \rangle$ that accepts $L$. There is a constant size circuit whose input is a symbol $\sigma$, and whose output is the function $...
Yuval Filmus's user avatar
4 votes
Accepted

How to compute (x MOD y) with just SUM and MULT gates?

Turing machines and circuits are very different models of computation: Turing machines are a uniform model and circuits are a non-uniform model. Turing machines accept inputs of an arbitrary length, ...
Yuval Filmus's user avatar
4 votes

Proving that EXP doesn't have polynomial-size circuits

You can consider a circuit as a directed graph where nodes are inputs and gates. For a circuit of size $n^k$ on input of size $n$, there are at most $(n+n^k)^2$ edges, and each node (gate) has three ...
xskxzr's user avatar
  • 7,455
4 votes
Accepted

Is it known that $AC^1 \subseteq L$?

Matrix powering shows that directed reachability is in $\mathsf{AC^1}$, and so $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC^1}$. In more detail, suppose that $A$ is the adjacency matrix of a ...
Yuval Filmus's user avatar
4 votes

Quantum NAND gate

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 ...
Craig Gidney's user avatar
  • 5,862

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