Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [circuits]

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

0
votes
1answer
23 views

Simplifying SOP: implementing OR with NAND

I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such: $a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$ In other ...
1
vote
1answer
47 views

The role of depth of a circuit in its hardware implementation

The depth of a circuit is the maximal length of a path from an input gate to the output gate of the circuit [Reference] Question: What is the relation between the depth of a circuit and hardware ...
0
votes
0answers
6 views

Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
0
votes
0answers
20 views

Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
0
votes
0answers
13 views

How does an accumulator with an upper and lower half work?

In the article "The IBM Magnetic Drum Calculator Type 650", originally published in Vol. 1, Issue 1 of Journal of the ACM, the article describes a computer architecture with a single accumulator ...
0
votes
0answers
14 views

Reducing weighted linear threshold gate to unweighted one

Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the ...
2
votes
2answers
45 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
17 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
43 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)$ ...
1
vote
0answers
19 views

Complexity class without fixed-poly size circuit

$PP$ is shown to have no fixed-poly size circuit by Vinodchandran. Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan. In notation, ...
1
vote
1answer
32 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
16 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
18 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
0answers
18 views

Monotone complexity of $s$-$t$ connectivity

In the problem STCONN, we are given a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between two given ...
0
votes
1answer
25 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
18 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
22 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
26 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: ...
0
votes
0answers
12 views

synchronous sequential circuits v/s asynchronous

I was studying about Advantage of synchronous sequential circuits over asynchronous ones and I am confused that which one has lower hardware requirement?
2
votes
2answers
88 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 ...
4
votes
2answers
107 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
14 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 ...
0
votes
0answers
18 views

Moore diagram circuit

Fig. 3-3 is a Moore type sequential circuit composed of a positive edge triggered D flip-flop and a combinational circuit. X is input, Y is an output, and CLK is a clock. Please show how Qo, Q1, and Y ...
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
19 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
29 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 ...
2
votes
1answer
32 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
67 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
62 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
60 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
30 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 \...
3
votes
1answer
230 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
42 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
58 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
31 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?
3
votes
0answers
35 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
37 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
25 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
32 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
261 views

Logic Circuits - Binary divisible by 16 [closed]

I have a question ...
3
votes
1answer
88 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'...
2
votes
2answers
119 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
54 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
904 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
22 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
137 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
30 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
26 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 ...
4
votes
1answer
295 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)$ ...