Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
3
votes
2answers
62 views

Weaker, but similar conditions to Turing completeness?

A model of computation is called Turing complete if it can simulate any Turing machine. This rules out for example a combinational logic circuit. However, there is a sense in which combinational ...
0
votes
0answers
20 views

Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits

I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is ...
2
votes
0answers
57 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
2
votes
1answer
206 views

Circuits vs Turing Machines in the “nonuniform model of computation”

I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the ...
0
votes
1answer
29 views

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
1
vote
0answers
29 views

Introduction to circuit complexity? [closed]

The books I'm reading on complexity theory primarily are about complexity of decision problems by Turing machines. I'm interested in computational complexity of circuits, both boolean and continuous ...
0
votes
1answer
55 views

Boolean Algebra Simplifying complex equation

I am trying to simplify the following equation and I am getting stuck on a line and I can't cut it down any further. I'm not sure if certain 'moves' are legal or not. F(A,B,C,D) = A'B'C' +ACD + A’BCD ...
2
votes
0answers
54 views

How to minimize the number of gates of an arithmetic circuit?

A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices. Consider an arithmetic circuit where the only operations are addition ($+$) and ...
1
vote
0answers
39 views

Equality checking mod $10$ via arithmetic circuits

I'm interested in implementing equality checking mod 10 in an arithmetic circuit. Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it ...
1
vote
1answer
33 views

Proof that a quantum computer is equivalent to some logical circuit

My question is about the quantum computer. I have tried to prove that the quantum computer is equivalent to some logical circuit. I know this has already been proven, but I will present my attempt: ...
2
votes
2answers
192 views

Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
5
votes
2answers
209 views

What does “AC0 many-one reduction” mean?

What does $\mathsf{AC^0}$ many-one reduction mean? I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.
1
vote
0answers
28 views

projection of arithmetic formulas to determinant

I am looking for a direct proof (i.e. without going through ABPs) that if $f(\bar{x})$ has an arithmetic formula of size $s$ then it is a projection of an $O(s)\times O(s)$ determinant. It seems ...
1
vote
0answers
17 views

What standardized formats (if any) exist for boolean circuits?

Being able to represent a Boolean circuit is useful in a number of areas of Computer Science, such as Circuit Satisfiability, Zero-Knowledge Proofs and Garbled Circuits. Are there any standards for ...
0
votes
1answer
22 views

terminology: half adders, full adders

I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders' I've read before that 'half adders' are called so, because two of them make up a 'full adder', ...
-1
votes
1answer
36 views

How can the binary OR function be computed by a MOD3 gate of constant fan-in?

I've been working on a problem and in order to prove the bigger picture, I need to understand how a binary OR function can be computed by a constant fan-in MOD3 gate. I would seem that the output ...
3
votes
1answer
62 views

Is it known that $AC^1 \subseteq L$?

A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
3
votes
0answers
154 views

Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? ...
2
votes
1answer
143 views

Space complexity of boolean circuit evaluation

I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size. Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$. Now, assuming the fan in of ...
1
vote
1answer
116 views

Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, ...
3
votes
0answers
31 views

Number of distinct single-assignment forms with $j$ binary function calls?

Given $n$ inputs and $k$ outputs and $j$ identical binary function calls to $g$, how many possible distinct single-assignment forms are there? The only assumption made about $g$ is that if $a = c \...
4
votes
1answer
352 views

Proving that EXP doesn't have polynomial-size circuits

How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$? I have a reminder that says $$ \mathrm{EXP} =\...
1
vote
1answer
100 views

On importance of Stockmeyer theorem

Theorem: (Stockmeyer, 1974) Any circuit that takes as input a formula (in the language of WS1S) with up to 616 symbols and produces as output a correct answer saying whether the formula is valid ...
3
votes
1answer
95 views

Number of non-XOR gates needed to implement an n-bit boolean function

There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits. A classic ...
1
vote
0answers
39 views

About sign-rank of Boolean functions

Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
2
votes
0answers
38 views

From SETH to circuit lowerbounds

Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR) In threshold ...
1
vote
1answer
43 views

How to compute (x MOD y) with just SUM and MULT gates?

It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates. By the way, I could not come up with designing $MOD$ ...
0
votes
0answers
37 views

Circuit Lower bound for $EXP^{NP}$

By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$. Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures). By using the ...
2
votes
1answer
133 views

Containment of ACC$^0$ in TC$^0$

The Complexity Zoo states that ACC$^0$ is contained in TC$^0$ and links to the paper On ACC and Threshold Circuits. However, what the linked paper proves is that depth-3 threshold circuits of ...
0
votes
1answer
400 views

Logic Circuits - Binary divisible by 16 [closed]

I have a question ...
2
votes
1answer
104 views

$ACC^{0}$ vs Poly-size circuits of bounded degree

We know that NEXP $\not\subset ACC^0$ (Ryan Williams'10 Result). Also, We know that even $\Sigma_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ (Kannan'...
3
votes
2answers
204 views

NP-hardness of MCSP

Ryan Williams and Cody Murray in 2015 proved that MCSP (Minimum Circuit Size Problem) is provably not NP-hard under local reductions. (Local reductions are the ones in which you are allowed time $O(n^{...
0
votes
1answer
63 views

LTF circuits and $AC^0$

Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights). For any vector $w \in \mathbb{R}^n$ and any number $c \in \...
0
votes
1answer
28 views

Taking mod $2$ with LTF gates

Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates? I do not mean that the ...
6
votes
1answer
1k views

How to show that hard-to-compute Boolean functions exist?

How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute? This problem was originally stated in Exercise 3.16 of Nielsen & ...
-1
votes
1answer
26 views

Some questions about the depth hierarchy of threshold circuits

Let me split my query into a few parts which possibly have overlapping answers, How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) ...
2
votes
1answer
267 views

Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
0
votes
1answer
36 views

Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks

My question stems from something mentioned in the following paper*: Acyclic Multi-Way Partitioning of Boolean Networks by Jason Cong, Zheng Li, and Rajive Bagrodia Given a DAG representing a Boolean ...
1
vote
1answer
52 views

CNF and small-depth circuits

I'm reading on small-depth circuits. Since every formula can be turned into a CNF formula, which has depth at most 3, why should we study deeper circuits? Is it because convertion to CNF may result in ...
6
votes
1answer
647 views

Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)

My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ ...
1
vote
2answers
376 views

Show that boring boolean circuit belongs to NP-complete class

We say that a boolean circuit is boring if it returns the same result for $>\frac34$ possible input, where we have $n$ input gates. Hence, boring circuit returns the same output ($0$ or $1$) ...
0
votes
1answer
109 views

Someone explain the Venn diagram for the logic equation (A+B)(B+C)

I posted a similar question here, however I have another question regarding Venn diagrams and logic circuits... In this problem: $$(A+B)(B+C)$$ Wouldn't the Venn diagram look something like this? ...
2
votes
2answers
174 views

Someone explain the venn diagram for the logic equation A*(B+C)

So, I am studying logic circuits and how to prove them with Venn diagrams. When drawing a Venn diagram for the equation A*(B+C) I figured it would look something like this: But according to the ...
0
votes
2answers
116 views

Decide if binary encoded number is divisible by 3

Let's consider the language over $\{0,1\}$ containing such words $w$ that: $$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + .. + m_n \mod 3 = 0$$ ($m_i$ we ...
1
vote
1answer
189 views

Show that problem is PSPACE-complete - path in directed graph

I have a following problem: Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...
1
vote
1answer
174 views

Caesar Cipher - logic circuit [closed]

my teacher asked the class to do a digial circuit that encrypted a message using cesar's cipher, and a circuit to decrypt, but my only idea is to solve it using a circuit that does P + K mod N, where ...
5
votes
1answer
105 views

Lower bound of degree of polynomial approximating parity

Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$ It is known [See e.g. Lemma 5 of this lecture note] that any ...
1
vote
1answer
68 views

Question on digital DE-MULTIPLEXER!

How does a demultiplexer ignore/discard/block the non-required outputs? A demultiplexer channels the input to one of the outputs, but there are several outputs. When one output is selected (depending ...
74
votes
9answers
18k views

Why is addition as fast as bit-wise operations in modern processors?

I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex ...
1
vote
1answer
62 views

small size and small depth circuit for set intersections

Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$. Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then ...