A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
74
votes
9answers
17k 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 ...
20
votes
2answers
5k 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?
18
votes
1answer
454 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 ...
11
votes
1answer
213 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.
10
votes
1answer
805 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 ...
10
votes
1answer
1k 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 ...
9
votes
1answer
357 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 ...
8
votes
3answers
423 views

Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
8
votes
3answers
268 views

Circuit size for “at least n inputs are true”

Say you have $m$ boolean inputs, and you are given a threshold $n$. You need to construct a boolean circuit that evaluates to true if at least $n$ of the inputs true. You may use AND, OR, NOT, or XOR ...
8
votes
1answer
1k views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation. I was wondering whether combinational ...
8
votes
1answer
117 views

Assumption on weights in threshold circuits

A threshold gate implementing a linear threshold function on $n$ boolean inputs $x_1, x_2 \ldots, x_n$ is given by the equation: $w_1 x_1 + w_2 x_2 + \ldots, w_n x_n \ge t$ where $w_1, \ldots, w_n, t \...
8
votes
1answer
1k views

Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace

Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped. Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a $C^n(...
8
votes
0answers
79 views

Connections between circuit complexity and Unique Games Conjecture?

Circuit complexity has connections to many questions in complexity theory. For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
7
votes
2answers
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 ...
7
votes
1answer
105 views

Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight

There is a basic result in circuit complexity that says: There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$. The argument is a simple counting argument on the ...
7
votes
1answer
217 views

How to relate circuit size to the running time of Turing machine

From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/, Define, $M_{[x,c]}$ as the deterministic Turing machine that operates as follows on an input $y$. The machine treats $...
6
votes
1answer
1k views

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

How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute? This problem was originally stated in Exercise 3.16 of Nielsen & ...
6
votes
1answer
200 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 ...
6
votes
1answer
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$
6
votes
1answer
3k views

Simple proof that circuit satisfiability problem is NP-Hard

$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS. $\cc = \{\langle C \rangle : C \text{ is a ...
6
votes
2answers
785 views

What circuit depth is required to add?

If we suppose that we are given two numbers $a$ and $b$ to add, what circuit depth do we require to add them? I'm wondering if $a$ and $b$ are $O(n)$, and thus the amount of bits required to store $a$...
6
votes
1answer
852 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 ...
5
votes
3answers
680 views

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

Every paper says that Green's construction is the best 16-input sorting network as for now. But why does Wikipedia says: "Size, lower bound: 53"? I thought "lower bound" meant:"If there exists at ...
5
votes
2answers
185 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.
5
votes
1answer
211 views

Simple lower bounds against AC0

It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \...
5
votes
1answer
166 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 ...
5
votes
1answer
61 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 ...
5
votes
1answer
99 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 ...
5
votes
1answer
221 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 ...
5
votes
2answers
884 views

Formulas vs Circuits

In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A ...
5
votes
1answer
81 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 ...
5
votes
1answer
109 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 ...
5
votes
1answer
180 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 ...
4
votes
1answer
97 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$ ...
4
votes
1answer
315 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 ...
4
votes
3answers
96 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 ...
4
votes
2answers
245 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 ...
4
votes
1answer
340 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. ...
4
votes
1answer
331 views

Proving that EXP doesn't have polynomial-size circuits

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} =\...
4
votes
4answers
1k 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 $...
4
votes
1answer
173 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 ...
4
votes
0answers
86 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 ...
4
votes
1answer
536 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)$ ...
4
votes
0answers
260 views

PARITY using depth one TC0 circuit

I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a ...
3
votes
2answers
173 views

Function that cannot be computed by a Boolean circuit of size $2^n/2n$

Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a ...
3
votes
2answers
120 views

Classical Computation without NOT

Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible ...
3
votes
3answers
256 views

Can a Boolean circuit be considered an algorithm?

Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single ...
3
votes
2answers
56 views

Weaker, but similar conditions to Turing completeness?

A model of computation is called Turing complete if it can simulate any Turing machine. This rules out for example a combinational logic circuit. However, there is a sense in which combinational ...
3
votes
1answer
100 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$...
3
votes
1answer
89 views

Number of non-XOR gates needed to implement an n-bit boolean function

There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits. A classic ...