# Tagged Questions

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

61 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 ...
354 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 ...
23 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 ...
31 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 ...
63 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 ...
26 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 ...
121 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 ...
100 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 ...
50 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 ...
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 ...
36 views

22 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 ...
74 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$ ...
27 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 ...
29 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$) ...
286 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 ...
30 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 ...
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.
40 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 ...
66 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 ...
33 views

58 views

64 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 ...
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 ...
148 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 ...
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 ...
349 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 ...
177 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 ...
56 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 ...
109 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 ...
82 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 ...
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 ...
97 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 ...
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 ...
103 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 ...
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?