Questions tagged [circuits]

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

23 questions
Filter by
Sorted by
Tagged with
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?
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 ...
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 ...
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 ...
280 views

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