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

learn more… | top users | synonyms

1
vote
0answers
26 views

Does an Expression in RPN Give us a Linear Way of Writing What Happens in a Circuit?

I mean, say we want to show how we can implement an OR gate in terms of a NAND gate. If we write in Polish notation, then we've suggested that the circuit takes the gates before the inputs. If we ...
0
votes
1answer
54 views

Computing a boolean function with a small formula

Suppose that $x = (x_1,\ldots,x_n)$ is a binary vector and $f(x)$ is a boolean function. Furthermore suppose $y = (y_1,\ldots,y_m)$ is a binary vector and that $F(x,y)$ is a binary formula of size ...
3
votes
1answer
45 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 ...
2
votes
1answer
33 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 ...
3
votes
1answer
39 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$
0
votes
0answers
42 views

2-depth arithmetic circuits and VP vs VNP

the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary: is this new paper Sums of ...
6
votes
1answer
133 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 ...
3
votes
2answers
79 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 ...
1
vote
2answers
31 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 ...
-2
votes
1answer
47 views

Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility

Given a gate called Nand with the following truth table: A | B | A Nand B ------------------ 0 | 0 | 1 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 We can ...
3
votes
1answer
101 views

Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$

I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the ...
0
votes
1answer
16 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 ...
5
votes
1answer
142 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 thinking whether combinational ...
0
votes
1answer
89 views

How do I build a read/write 4-nibble RAM memory system using flip flops?

Currently, I'm learning about flip flops and how it is used in RAM to store memory so I'm trying to recreate the circuitry in Logisim. I know the components I need which are address register, 4-bit ...
3
votes
1answer
43 views

2-SAT or 3-SAT or k-SAT in AC-0

This may be an elementary question, but I'm new to circuit complexity. Does 2-SAT in CNF form belong to the complexity class AC$^0$? It seems simple enough to construct an AC$^0$ circuit of depth 2 ...
3
votes
1answer
67 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 ...
1
vote
1answer
76 views

What complexity class is this ciruit problem?

I'm exploring an algorithm that solves k-SAT. It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds. Without knowing the runtime, I speculate on how quickly it will ...
1
vote
0answers
23 views

How do I triangularise a netlist?

I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will ...
0
votes
0answers
63 views

Creating branch less than equals zero MIPS instruction in single cycle circuit

As a project I'm trying to implement a MIPS processor. I have a circuit similar to the one below. My question is what would be a way to implement a ...
3
votes
1answer
79 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 ...
2
votes
0answers
44 views

AC0 and first order logic equivalence

The page on descriptive complexity theory in Wikipedia states the following: "First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of ...
0
votes
1answer
55 views

How to design xml schema for digital circuits? [closed]

how can i design XML Schema for logical and digital circuits? i cant find any help or manual for this work for example i have a digital circuits with AND OR NOR ,... gates now i want design xml ...
2
votes
1answer
44 views

NP-complete problems and sub-expenential sized circuits

If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?
0
votes
0answers
32 views

Simplifying circuits using boolean algebra

I am having a lot of trouble simplifying my circuit using boolean algebra. I am very new to this and any explanation would be greatly appreciated. I have y'+z+w'x+wx' I feel like I could use ...
1
vote
0answers
26 views

Is VHDL a description language for a Boolean circuit or are both concepts unrelated

I am looking for a way to translate basic c programs (subset of c or java or some declarative programming language) to a Boolean circuit. I know that Turing machines are reducible to Boolean circuits ...
2
votes
1answer
263 views

Create a shallow logic circuit that increments a binary number

This circuit should be reasonably efficient in size and depth, but with priority on depth. If depth was not a concern, then I guess I could make a specialized adder for the least significant bit and ...
0
votes
1answer
54 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
31 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
44 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
59 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
120 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 ...
4
votes
2answers
83 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
84 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
123 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
116 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
93 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
97 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 ...
3
votes
3answers
193 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 ...
1
vote
1answer
164 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
1k 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 ...
8
votes
1answer
466 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
98 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
70 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
183 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
79 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
158 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
137 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
170 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
90 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
239 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 ...