Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
79 views

How can languages that are E-complete have sub-exponential size circuits?

The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta > 0$ is open, and this would imply some derandomization results. ...
2
votes
1answer
543 views

Regular Languages in $ \mathsf{\text{}NC^1}$

Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$. To prove the theorem stated above we need some theorems and definitions given below : Barrington Theorem : A branching ...
1
vote
0answers
95 views

How many bits we can negate using two/three NOT gates?

How many bits we can negate using two/three NOT gates ? I am newbie at this subject so I ask for help. It is about circuits. Edit After reading link given in comments by @D.W I think that I can ...
1
vote
1answer
109 views

Boolean circuit with two inputs and advice input is hard-wired

Claim : $\cup_{c,d} $ DTIME$(n^c)/n^d \subseteq$ $P_{poly}$ Proof : if $L$ is decidable by a polynomial-time Turing machine $M$ with access to advice family $\{\alpha_n\}_{n\in \mathbb{N}}$ of size $...
0
votes
1answer
80 views

Given snapshot and boolean circuit how to compute coNP formula?

Theorem 6.20: If $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$ then $\mathsf{EXP\text{}} = \Sigma_2 ^{p}$. My attempt : Let $L \in \mathsf{EXP\text{}}$. Then $L$ is computable by an $2^{p(...
3
votes
2answers
290 views

Function that cannot be computed by a Boolean circuit of size $2^n/2n$

Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a ...
7
votes
1answer
1k views

Given a Turing machine , How to construct a efficient boolean circuit?

The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page ...
2
votes
2answers
106 views

Given a function and its complexity, what is the complexity of its circuit?

For example, given an element-wise function $f$, with input $x\in\{0,1\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also ...
0
votes
2answers
3k views

Adjacency-list to Adjacency matrix in logarithmic space?

Input : Adjacency-list representation of Directed acyclic graph (Boolean circuit). see Complexity theory by Arora and bark, page no- 104 Find : Adjacency matrix representation of DAG (Boolean ...
1
vote
1answer
245 views

Computing snapshot of Turing machine from previous snapshots in logarithmic space?

To prove that $P \subseteq P_{\ poly}$ [see book by Arora and Barak, chapter 6, page no 105] Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \{0,1\}^* $ be some input for $M$...
2
votes
1answer
75 views

$\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?

Now, I have the following conjecture. $\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$. However, I am at a loss at ...
1
vote
0answers
689 views

3 bit binary multiplier?

I have the following 2-bit binary multiplier How can I modify this 2-bit binary multiplier to make it a 3-bit binary multiplier? I notice that there are 2 half-adders, and there are a bunch of ANDs ...
1
vote
1answer
157 views

Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting

Let me define the problems first Polynomial Identity Testing $(\mathsf{PIT\text{}})$ Given : A polynomial $p$ over some field $\mathbb{F}$. Decide : Are all coefficients of the monomials of $p$ ...
20
votes
1answer
623 views

Why do all recent SAT solvers work on CNF instead of circuit SAT?

After the release of the AIGER library to handle and-inverter graphs sometime in 2006 (I think), some circuit SAT solvers were released in 2006-2008, and in a few SAT Races/Competitions there were AIG ...
5
votes
1answer
198 views

Size of constant depth circuit for digital comparator?

Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers? Two $n$-bit binary numbers can be compared using a digital ...
0
votes
0answers
75 views

Division circuit - problem

I have a question about the logic circuit performing the division ( http://userpages.umbc.edu/~squire/cs313_l20.html ). I implemented it to some software but does not work. I drew the schematic ...
2
votes
1answer
124 views

Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?

I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has ...
1
vote
1answer
48 views

Circuit of constant depth that takes three binary numbers and outputs two binaries?

How can I construct -- or better to say what type of circuit can be like this -- a circuit that takes 3 binary numbers (a, b, c) and then calculates two binary numbers (d, e) in a way that ...
4
votes
3answers
99 views

Is it possible to determine if C=A+B faster than adding A+B in logical circuits

With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B. I know that it is possible to just determine the longest the circuit ...
0
votes
1answer
609 views

Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state?

Cause applying H (hadamard gate) on a state |0> will evolve to 50% |0> and 50% |1>, assuming we are meausring along the vertical axis (Z-axis). While applying a measurement along a horizontal axis (e....
8
votes
0answers
83 views

Connections between circuit complexity and Unique Games Conjecture?

Circuit complexity has connections to many questions in complexity theory. For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
3
votes
2answers
828 views

What are the gates used to implement Shor's algorithm?

I understand theoretically how Shor's algorithm works, but I don't know what specific gates are used (or would be used) to implement it. What would the quantum circuit look like?
2
votes
1answer
62 views

What are the gap functions in the $AC$ hierarchy?

Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of ...
1
vote
1answer
59 views

Proving that quantum circuits not involving entanglement are inefficient

I heard in a video that it can be proven that quantum circuits not involving entanglement can be efficiently simulated on a classical computer; i.e., that there is no point to building quantum ...
5
votes
1answer
123 views

Finding minimal and complete test sets for circuits

I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the ...
2
votes
3answers
219 views

Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters? An asynchronous multiplier is much bigger than an adder. It's about 18*n^2 NOR gates where n is the number of ...
5
votes
3answers
759 views

Is Green's the best 16-input sorting network so far?

Every paper says that Green's construction is the best 16-input sorting network as for now. But why does Wikipedia says: "Size, lower bound: 53"? I thought "lower bound" meant:"If there exists at ...
2
votes
1answer
71 views

Checking membership in DFA with fixed length using AC1 circuit?

I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should ...
2
votes
1answer
265 views

What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates

In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...
1
vote
3answers
5k 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 ...
0
votes
1answer
630 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
1answer
187 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
169 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 ...
4
votes
1answer
875 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
375 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
135 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 $s(n)...
1
vote
1answer
111 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 $O(n^c)$ ...
1
vote
1answer
44 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
110 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
1answer
79 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$) ...
4
votes
4answers
2k views

Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates

A Boolean function $f : \{0, 1\}^n → \{0, 1\}$ is called monotone if changing any of the $n$ input bits $x_1, \ldots , x_n$ from $0$ to $1$ can only ever change the output $f(x_1, \ldots ,x_n)$ from $...
8
votes
3answers
490 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 ...
1
vote
1answer
245 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
27 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.
0
votes
1answer
56 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 ...
5
votes
1answer
186 views

Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

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
70 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
32 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 direction?...
2
votes
1answer
219 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
127 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 ...