A computation model in which the computation is described via circuits of various logic gates.
4
votes
1answer
44 views
What is the exact difference between a latch & a flipflop?
From what I have understood :
A Flip Flop is a clocked latch i.e. flip flop = latch + clock
Latch continuously checks for inputs & changes the output whenever there is a change in input
Flip ...
1
vote
1answer
83 views
Why S=1, R=1 Is forbidden in RS-Flip Flop [closed]
I have come across about RS Flip Flop & I have tried implementing that on a simulator & using actual logic gates. But I'm still not sure whether I have correctly understood the case unstable ...
1
vote
2answers
62 views
Why is the name half-adder used to represent the half-adder?
I have recently came across half-adders and full adders in my Logic Network lectures. I have somewhat understood the theory, but I am still unable to understand the reason why they called them in that ...
6
votes
1answer
63 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 ...
3
votes
0answers
51 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 ...
6
votes
1answer
46 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 ...
2
votes
2answers
35 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 ...
2
votes
2answers
28 views
What does “number of gates” mean in circuit complexity?
By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.
-1
votes
1answer
42 views
Circuit Maker repalcement [closed]
I'm studying CS, and we have a course called "computer systems architecture" which is merger of two former "logic systems theory" and "mips asm" courses (I hope my translations are correct).
We have ...
3
votes
2answers
77 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 ...
4
votes
1answer
92 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 ...
7
votes
1answer
113 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.
3
votes
2answers
31 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 ...
2
votes
1answer
68 views
Building functionally complete boolean circuits out of trinary logic
There are some not-very-commonly considered forms of trinary logic using 3 truth values. Even entire (unusual/rare) ternary computers have been built from it.
Is there some knowledge or reference ...
3
votes
1answer
95 views
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 ...
7
votes
1answer
52 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 ...
3
votes
1answer
67 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.
...
5
votes
2answers
147 views
Circuit size for “at least n inputs are true”
Say you have m boolean inputs. You need to construct a boolean circuit (using gates that map two booleans to one, e.g.: AND, OR, NOT, XOR, ...) that evaluates to true if at least n (n < m) are ...
7
votes
1answer
142 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 ...
7
votes
2answers
354 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?
