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

learn more… | top users | synonyms

1
vote
2answers
40 views

Sum of 3 integers with full adder

1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image ...
1
vote
1answer
24 views

Utility of D latch/flip-flop and how it differs from an SR latch/flip-flop

I understand that in a D latch, whenever the clock signal is high, Q matches D, and while the clock signal is low, it holds the previous state of D. For a D flip-flop, Q will hold whatever value D is ...
5
votes
0answers
115 views

Amortizing or batching circuit evaluation for many different inputs?

Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k*2^n)$ simply by calculating all the intermediate values ...
1
vote
0answers
95 views

On power of $P/poly$

(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close? (2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the ...
1
vote
1answer
42 views

Converting Boolean circuit to Boolean formula in parallel

Let t be a fixed constant. I would like to convert a Boolean circuit C of depth t on n inputs over AND, OR and NOT gates (of fan-in 2, say) to an equivalent Boolean formula F on the same n inputs, in ...
2
votes
2answers
46 views

Is there a canonical form that uses AND and XOR?

Is there something like the sum of products form of a circuit which uses AND and XOR instead of AND and OR? I know that you can create an OR gate from AND and XOR (but i can't remember or find the ...
1
vote
1answer
35 views

A function computable using a circuit of size $10s$ but not of size $s$

I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help. Prove that for every function ...
1
vote
1answer
22 views

Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?

Sanjeev Arora and Boaz Barak show the following : $P/poly = \cup_{c,d} DTIME (n^c)/n^d$ where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$ and runs in ...
1
vote
1answer
19 views

What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit?

I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant ...
4
votes
1answer
72 views

On relation between FFT and polynomial multiplication

Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ ...
1
vote
0answers
25 views

On formula complexity of permanent

Is it consistent with our knowledge that $VNP=VP$ and/or $Permanent\in P$ but still formula complexity for permanent is large? If so what would exponential formula size for permanent give and why ...
1
vote
1answer
28 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
3answers
278 views

Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
2
votes
1answer
28 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 ...
1
vote
0answers
26 views

Arithmetic problems known to be in TC^{i+1} but not known to be in TC^i

Is there an arithmetic problem that is known to be in $TC^{i+1}$ but not known in $TC^i$ for any $i\geq0$? Concrete examples for $i=0$ would be of most utility however any arithmetic example is fine.
1
vote
1answer
39 views

*non-uniform* $ACC^0$ and above classes

$NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$. We do not know if either $NP$ or $P/poly$ is in $ACC^0$. Suppose every problem in $NP$ can be solved in polynomial time ...
2
votes
1answer
65 views

Difference between $\mathsf{SIZE}(n^k)$ and $\mathsf{P/poly}$

In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which ...
1
vote
1answer
33 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\\ ...
2
votes
0answers
22 views

What are the recent research directions in the topic of circuit lower bounds from derandomization?

I am thinking of the classical paper, https://www.cs.sfu.ca/~kabanets/Research/poly.html Can someome link to some papers/reviews that give a sampling of what are the recent thoughts in this ...
2
votes
1answer
40 views

Time complexity of minimizing Boolean expression

Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used. The following Wikipedia article ...
3
votes
2answers
99 views

Classical Computation without NOT

Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible ...
3
votes
1answer
30 views

How many inputs does the Hadamard gate have?

Look at the diagram in the middle of page 6-3 here, http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf I am confused as to how should one think ...
1
vote
0answers
35 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
65 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
55 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
84 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
187 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
61 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
153 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 ...
4
votes
1answer
178 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
61 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
84 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
146 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 ...
1
vote
1answer
31 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
334 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 ...
0
votes
1answer
169 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
55 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
105 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
81 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
30 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 ...
4
votes
1answer
94 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
60 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
101 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
48 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
44 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
30 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
494 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
149 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
40 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!
7
votes
1answer
52 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 ...