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

learn more… | top users | synonyms

1
vote
0answers
7 views

Question about Kannan's theorem [migrated]

I was reading a paper of Buhrman and Homer "Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy" ...
0
votes
1answer
22 views

Circuits for Modular Arithmetic

I've read this which describes how to do do integer arithmetic in circuits. The one thing that it does not describe is how to do these operations with a modulus. How can modular arithmetic be done in ...
1
vote
1answer
22 views

How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there? [closed]

For simplicity, we can assume that only NAND gates are allowed. An asymptotically correct solution is all I really need. Thanks!
6
votes
1answer
33 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
1answer
45 views

Assume that SAT ∈ PSIZE, does it imply that NP = coNP?

Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ? I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ ...
1
vote
1answer
45 views

Relation between logspace-uniform circuits and P-uniform circuits

In the book "Computational complexity" of Barak and Arora, on page 112, they state that: Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P. The proof of ...
3
votes
1answer
29 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 ...
2
votes
1answer
57 views

Computing parity function on n variables with O(n) gates

Sipser example 9.29 He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same ...
2
votes
1answer
58 views

Emulating boolean circuits using addition and multiplication (mod 5)

I'm trying to use gates that do addition and multiplication modulo 5 to emulate logic gates. Assuming false and true are mapped to 0 and 1 respectively (with 2, 3, and 4 being invalid), I figured out ...
5
votes
1answer
76 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 ...
1
vote
0answers
64 views

Functional Unit and Micro-operations Schematics

I'm sitting an exam on Computer Architecture in a few days and i'm stuck on a particular type of question. I'm asked to: Provide a detailed schematic for a functional unti that implements the ...
1
vote
2answers
58 views

How to design this synchronous circuit?

I have seen this model question on synchronous circuit , but i could not understand the logic, can anyone please help me? "Develop the state diagram for a synchronous sequential circuit which will ...
2
votes
2answers
142 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 ...
4
votes
1answer
848 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
125 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
3answers
711 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 ...
7
votes
1answer
234 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
69 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
59 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
102 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
52 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.
3
votes
2answers
123 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
108 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 ...
9
votes
1answer
146 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
58 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
155 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
232 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
59 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
82 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. ...
8
votes
3answers
195 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
164 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
878 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?