# Tag Info

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

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

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

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

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

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

Accepted

### What is the decidable language in $P/poly$ but not in $P$?

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

### Is there an intuitive proof for the existence of hard functions?

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

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

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

Any Boolean function can be written as a DNF. Each clause in the DNF specifies one truth assignment for which the function holds. For example, the DNF form of XOR is $(x \land \lnot y) \lor (\lnot x \... 7 votes ### Isn't polynomial identity testing over arithmetic *expressions* trivial? 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$... 7 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 ... 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 & ... 6 votes Accepted ### Difference between$\mathsf{SIZE}(n^k)$vs$\mathsf{P/poly}$and$\mathsf{SIZE}(n)$vs linear size circuit?$\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 ... 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 ... 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 ... 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 ... 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 ... 6 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 ... 5 votes Accepted ### Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace Eventually I ended up solving this for$O(n)$gates. I wrote up a trilogy of blog posts on it. Constructing Large Controlled Nots (classically, with an ancilla) Constructing Large Increments (... 5 votes ### An AC$^1$circuit for 2-SAT The proof that$\mathsf{NL} \subseteq \mathsf{AC}^1$is constructive, giving an$\mathsf{AC}^1$circuit for directed reachability. Since directed reachability is$\mathsf{NL}$-complete and 2SAT is in$...
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})$). ...
### 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 \$\...