# Questions tagged [circuits]

A computation model in which the computation is described via circuits of various logic gates.

258 questions
Filter by
Sorted by
Tagged with
20k views

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

I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex ...
6k views

### Universality of the Toffoli gate

Regarding the quantum Toffoli gate: is it classicaly universal, and if so, why? is it quantumly universal, and why?
627 views

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

After the release of the AIGER library to handle and-inverter graphs sometime in 2006 (I think), some circuit SAT solvers were released in 2006-2008, and in a few SAT Races/Competitions there were AIG ...
259 views

### Which non-regular languages are in $AC^0$?

For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.
1k views

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

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
471 views

### Depth-2 circuits with OR and MOD gates are not universal?

It is well-known that every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates ...
2k views

### How to understand the SR Latch

I can't wrap my head around how the SR Latch works. Seemingly, you plug an input line from R, and another from S, and you are supposed to get results in $Q$ and $Q'$. However, both R and S require ...
2k views

83 views

1k views

### Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)

My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ ...
1k views

### Given a Turing machine , How to construct a efficient boolean circuit?

The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page ...
1k views

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

Does there exist an equivalent arithmetic circuit for each computable function? I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe ...
223 views

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

I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by ...
2k views

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

Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
3k views

187 views

### Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which ...
82 views

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

In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies ...
129 views

### Lower bound of degree of polynomial approximating parity

Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$ It is known [See e.g. Lemma 5 of this lecture note] that any ...
236 views

### Modulo operation in monotone complexity

Given $x\in\Bbb N$, I would like to find $x\bmod N$, where $N$ is composite. For example $N=35$, $x=53$ and $x\bmod N=18$. Is this operation considered monotone in circuit/algebraic complexity ...
513 views

How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$? I have a reminder that says $$\mathrm{EXP} =\... 1answer 132 views ### Finding minimal and complete test sets for circuits I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the ... 1answer 71 views ### Is there a polynomial sized arithmetic formula for iterated matrix multiplication? I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow ... 1answer 205 views ### Size of constant depth circuit for digital comparator? Is a lower bound of \Omega(n^2) known for the size of any constant depth circuit expressing a digital comparator for two n-bit numbers? Two n-bit binary numbers can be compared using a digital ... 1answer 187 views ### Amortizing or batching circuit evaluation for many different inputs? Suppose that I have a boolean function of size k with n inputs. I would expect to be able to evaluate it on all possible inputs in time O(k*2^n) simply by calculating all the intermediate values ... 1answer 111 views ### On relation between FFT and polynomial multiplication Is it known that if polynomial multiplication of degree n polynomials and coefficient size bounded by M can be done in O(n) arithmetic operations on O(\log n+\log M) bit sized words then FFT ... 4answers 2k views ### Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates A Boolean function f : \{0, 1\}^n → \{0, 1\} is called monotone if changing any of the n input bits x_1, \ldots , x_n from 0 to 1 can only ever change the output f(x_1, \ldots ,x_n) from ... 1answer 118 views ### An AC^1 circuit for 2-SAT We know that NC^1 \subseteq NL \subseteq AC^1 and that 2-SAT is complete for NL. How does one construct an AC^1 circuit for 2-SAT? Recall that AC^1 circuits have O(\log n) depth where n... 3answers 99 views ### Is it possible to determine if C=A+B faster than adding A+B in logical circuits With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B. I know that it is possible to just determine the longest the circuit ... 2answers 290 views ### Creating a logical circuit Task: Design a 2 bit comparator. Input: 2x 2 bit (I take it as 2 2-bit values, let them be unsigned for simplicity) Output: 1 if result input1>input2 is true, 0 otherwise Develop truth table and ... 1answer 385 views ### Universality of NOT and CNOT I'm trying to figure out why NOT and CNOT gates are not sufficient to create all bijective functions in classical circuits. I have been struggling on this for hours, and just can't make sense of it. ... 2answers 272 views ### NP-hardness of MCSP Ryan Williams and Cody Murray in 2015 proved that MCSP (Minimum Circuit Size Problem) is provably not NP-hard under local reductions. (Local reductions are the ones in which you are allowed time O(n^{... 1answer 52 views ### Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k? Traditionally, the W hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class W[t] is defined as the closure under \mathrm{fpt}-reductions of the ... 1answer 883 views ### Converting Boolean circuit to Boolean formula in parallel Let t be a fixed constant. I would like to convert a Boolean circuit C of depth t on n inputs over AND, OR and NOT gates (of fan-in 2, say) to an equivalent Boolean formula F on the same n inputs, in ... 1answer 212 views ### How to find degree of polynomial represented as a circuit? I know very little about arithmetic circuits, so maybe it is something well-known. Given a small circuit consisted of \{1,x,-,+,*\} defining one variable polynomial. Let be additionally known that ... 0answers 44 views ### Problems that are easy on boolean formulas but become NP-hard on circuits? Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input? ... 0answers 130 views ### Perfect Halver Construction? A sorting network is a circuit-based approach to sorting, built out of CompareExchange gates, which compute the function:$$\mathsf{CompareExchange}(x,y) = (\min(x,y), \max(x,y)) The input to the ...
Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone ...