# Questions tagged [circuits]

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

258 questions
Filter by
Sorted by
Tagged with
36 views

30 views

### Decidable languages unconditionally not in P/poly

What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones? I'm interested in unconditional results rather than examples such as the Karp–Lipton ...
25 views

### Make the forward counter go down

Suppose, I have a 4-bit binary Incrementor that uses XOR gates to increment the inputted number by the value of 1 (b0001, to be precise). Suppose, we connect it to 4 D-Flip-Flops (DFF) to create a ...
23 views

### Number of possible boolean functions in a DAG of lookup tables?

A K-input lookup table (K-LUT) can represent any function with K boolean inputs and a single boolean output. The number of possible functions represented by this LUT is $2^{2^K}$ according to this ...
61 views

### How does fan-out change circuit complexity?

Edit: Here's maybe a clearer presentation of my question. In a Boolean formula, all the gates have fan-out 1, and the graph representing the formula is a tree. In a Boolean circuit, the gates can have ...
72 views

### Details wanted on the reduction from Circuit Value to CFG Membership

Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a ...
15 views

### Mechanism of Howard's algorithm

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?
28 views

### What was the original paper that showed a simulation of turing machines via circuits?

It is a very standard construction in most complexity theory courses to turn a turing machine into a circuit. I thought this was due to Cook, but it looks like he did the reduction to SAT not through ...
52 views

32 views

### Comparing PRAM and Circuit Complexity, $NC^i$

I wondered about the following quote from NC (Wikipedia): $NC^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and ...
30 views

### Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?

Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table 00 0 01 0 10 0 (*) 11 1 but such that the case (*) is wrong 1/3 of the time, ...
58 views

### Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?

Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
36 views

### Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$

I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates, and the negation is applied only to input variables. So, assuming we have a ...
26 views

### How can you convert the depth of a boolean circuit to its size?

I know that the depth of a circuit is the maximal length from an input gate to the output gate of the circuit and its size is its number of gates. Is there a formula that you can go from depth to size ...
44 views

### Problems that are easy on boolean formulas but become NP-hard on circuits?

Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input? ...
41 views

### Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?

Let $\mathcal C$ be a circuit of $m=f(n)$ input wires where every input is taken in the set $\{x_1,x_1',\dots,x_n,x_n'\}$ where $x_n\in\{0,1\}$ and $x_n+x_n'=1$ holds (not all $x_i,x_i'$ necessarily ...
102 views

30 views

### What is uniformity in Boolean circuits exactly?

I have two questions on Kaveh's answer to Definition of uniform boolean circuit : Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a ...
27 views

### How to find the reverse of a binary string with simple binary operators?

I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome? So my approach is to feed the input to a circuit that reverses the input, ie if ...
21 views

### Newbie 2s complement to binary circuits help

I'm creating a circuit with in3, in2, in1, and in0, and outputs F11-F0. The circuit has to take the input in 2s complement and output the number in binary with the sign. F11 represents the sign bit (...
20 views

### Circuits and Closure Under Reductions

Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$? Using similar ideas like Cook-Levin (...
60 views

### Symmetric functions in NC¹

A boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$. It is known that every boolean function is in $\mathrm{NC}^1$, i.e. there ...
38 views

### Were boolean logic used in the analog computers?

I began a simple collection of the events behind todays computers. My knowledege in these fields is so limited, and I read: "In the 1930s and working independently, American electronic engineer ...
28 views

### Generalizing Quantum Computation

When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to ...
107 views

### Closure properties of Alternating Circuit 1 level

Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth. Is this class closed under Kleene star? I thought it would be simple since it is ...
28 views

168 views

### Is NP in NP/Poly?

The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice ...
23 views

### single circuit simulating multiple Turing machines

You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?
19 views

### Simulation of circuits with circuits

From classical results of universal simulation of Turing machines there exists a Universal Turing machine simulating any Turing machine with time complexity 𝑇(𝑛) in time 𝑇(𝑛)log𝑇(𝑛). Is there is ...
37 views

### Hardness of boolean functions

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of ...