Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
1answer
13 views

Programs to circuit conversion

Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME[f(n)]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates? How about when ...
2
votes
1answer
20 views

Satisfiability Toward A Sequential Circuit

Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean ...
2
votes
0answers
26 views

Implementing depth-3 circuit for XOR

In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR. I tried for a little bit to figure out how to do this, but couldn't find ...
9
votes
1answer
748 views

Why isn't P and P/poly trivially the same?

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
1
vote
2answers
61 views

Quantum NAND gate

Wondering how a quantum NAND gate would be implemented, and if it would be considered universal. I saw for quantum computing the Hadamard, phase, CNOT and π/8 gates are universal, but didn't see NAND ...
1
vote
2answers
62 views

If a NAND gate is universal, why you don't have NAND OISCs

If a NAND gate can be used to construct all other of the basic logic gates, then I'm wondering why you don't/can't have a purely NAND-based One Instruction Set Computer (OISC). All the OISC single ...
0
votes
2answers
54 views

How “add” could be implemented in only bitshift operations

Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift ...
1
vote
0answers
31 views

Best-known Boolean Circuits for Clique? [closed]

Not having received a satisfactory response to this question in math.SE, I am asking it here: In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
0
votes
1answer
58 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
54 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 ...
1
vote
1answer
16 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
26 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
16 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
19 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 ...
3
votes
2answers
50 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
19 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
47 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
20 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
105 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
20 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
23 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
38 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
24 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
27 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
13 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
118 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
143 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
21 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
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
30 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
40 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
104 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
88 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
74 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 \...
3
votes
1answer
265 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
72 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
68 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
35 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
40 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
28 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
56 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
320 views

Logic Circuits - Binary divisible by 16 [closed]

I have a question ...
2
votes
1answer
95 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
158 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
57 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 ...