# Questions tagged [circuits]

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

249 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?
604 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 ...
255 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 isn'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 ...
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 ...
456 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

83 views

916 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 ...
306 views

### What does “AC0 many-one reduction” mean?

What does $\mathsf{AC^0}$ many-one reduction mean? I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.
212 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

182 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 ...
77 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 ...
119 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 ...
231 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 ...
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 111 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 62 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 183 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 186 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 108 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 ... 1answer 377 views ### What is the relation between arithmetic circuits and straight line programs? One definition of arithmetic circuits is as follows: An arithmetic circuit \Phi over the field \mathbb F and the set of variables X usually, X = \{x_1, \dots , x_n\}) is a directed acyclic ... 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 116 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 287 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 381 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 254 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 51 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 844 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 208 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 42 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 129 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 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 circuit? ...