Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
21
votes
2answers
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?
4
votes
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 ...
10
votes
1answer
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 ...
4
votes
0answers
194 views

Simple example of exponential gap between monotone and non-monotone circuits

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 ...
7
votes
1answer
280 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 $...
7
votes
1answer
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 ...
3
votes
1answer
399 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 ...
1
vote
1answer
112 views

Polynomial Identity Testing Evaluating a polynomial on a circuit

Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...
11
votes
1answer
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 ...
8
votes
1answer
2k 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
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$
2
votes
2answers
489 views

Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?

I'm working on exercise 4.29 of Nielsen and Chuang: Find a circuit containing O(n^2) Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n >3), using no work qubits. As ...
1
vote
1answer
79 views

Unconditional arithmetic circuit lower bounds for permanent/determinant

In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) ...
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 ...
7
votes
1answer
175 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 ...
3
votes
2answers
311 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 ...
1
vote
1answer
70 views

Algorithms for logical synthesis

Let's say that I want to map some string of binary digits to a single binary digit of output, like the below: $ \begin{array}{l|l} \text{Input}&\text{Output}\\ \hline 0001&0\\ 0011&1\\ ...
3
votes
2answers
985 views

Definition of uniform boolean circuit

Definition A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/...
2
votes
2answers
192 views

Someone explain the venn diagram for the logic equation A*(B+C)

So, I am studying logic circuits and how to prove them with Venn diagrams. When drawing a Venn diagram for the equation A*(B+C) I figured it would look something like this: But according to the ...
2
votes
1answer
527 views

How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?

The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$. The ...
2
votes
1answer
85 views

Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?

A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT ...
1
vote
1answer
32 views

Relationship between circuit size and formula size in Sipser text

The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can ...
1
vote
1answer
247 views

Why is c) a combinational circuit, but d) not?

I am doing practice after just learning what combinational circuits are, yet I am unsure of why (c) is combinational, but (d) is not. Can someone please explain to me why this is? The Solution ...