Skip to main content

Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
110 views

Deducing upper bound for Boolean Circuit size from well-known algorithms

Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the size of the minimal Boolean circuit C that calculates f? I think that it ...
Dudi Frid's user avatar
  • 231
4 votes
0 answers
41 views

"Small" formulas for boolean functions

Theorem 10 in the following document: https://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec1.pdf states that every boolean function $f:\{0, 1\}^n\rightarrow \{0, 1\}$ has formula complexity $O(...
hello_123's user avatar
  • 141
1 vote
2 answers
162 views

Binary logarithm of binary number using logic gates

I need to use logic gates to calculate the floor of binary logarithm of a binary number $x_{n-1}, ..., x_0$. I know that this can be computed when I find the position of the most significant bit set ...
popcorn's user avatar
  • 183
1 vote
2 answers
122 views

Check if n-bit number is divisible by 7

Show how to check if n-bit number is divisible by 7 in logarithmic circuit depth. How can I construct the circuit to be able to check the divisibility?
popcorn's user avatar
  • 183
0 votes
0 answers
17 views

Does $\mathsf{NC_1\subsetneq NC}$ imply $\mathsf{NP\neq coNP}$?

Any $\mathsf{NC}$ circuit could be presented in SAT form via Tseytin transform. This applies in the reverse too: an arbitrary SAT instance could encode any $\mathsf{NC}$ circuit. Now, Frege proof ...
rus9384's user avatar
  • 1,726
0 votes
1 answer
105 views

Can you compute a majority function of n-bits using an O(n) size circuit?

Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like? I have a feeling it has ...
circuitman324's user avatar
6 votes
1 answer
713 views

Representing binary functions with a finite gate set without exponential blow-up?

It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the ...
Andrew Baker's user avatar
0 votes
0 answers
11 views

$UCOUNT\leq_{cd} BCOUNT$

Suppose we are given $n$ bits $a_0,\dots, a_{n-1}$. Then let $s=\sum\limits_{i=0}^{n-1}$ Then $BCOUNT(a_0,\dots,a_{n-1})=s$ and $UCOUNT(a_0,\dots,a_{n-1})=1^s0^{n-s}$ Now i have to show that $UCOUNT\...
Soham Chatterjee's user avatar
0 votes
3 answers
86 views

Is there a 2SAT encoding for a NAND gate

I am trying to encode some circuit checking algorithms, but encountered difficulty creating a 2SAT representation for a NAND circuit. Is there a proof that this is not possible?
Hovercraft2's user avatar
0 votes
1 answer
53 views

Given a language L how can I derive its Boolean formula?

Let: be given by Compute Boolean formulas for the following: This is part of my coursework; I have the answers but can't understand them. I want to develop some intuition on how I can solve these ...
neferpitou's user avatar
0 votes
0 answers
43 views

Investigating the Claim: co-$NP\subseteq NP\text{/}P$ implies $\Sigma_3^P=\Pi_3^P$ and Collapse of the Polynomial Hierarchy?

I have been studying the polynomial hierarchy recently, and I came across an intriguing claim that I would like to explore further: Assuming co-$NP\subseteq NP\text{/}P$, the claim states that it ...
Straw User's user avatar
0 votes
0 answers
18 views

Are there any typical papers on the impossibility of black-box reduction of circuits?

I am now considering the impossibility of black-box reductions between error-correcting codes and universal hashing without multiplicative overhead in depth. I could hardly find any classical papers ...
Kagura Hitoha's user avatar
0 votes
0 answers
23 views

Logical circuit for priority resolution in interrupt controllers (with configurable priority, not fixed)

I'm interested in what the typical solution is for priority resolution in interrupt controllers. I assume a hardware logic circuit is used, and not software. For interrupt controllers with fixed ...
BipedalJoe's user avatar
0 votes
0 answers
16 views

Computational power of Turing machines vs circuit ensemble

Is it true that for every Turing machine 𝑀, there exists a circuit ensemble 𝐶 such that 𝐿(𝑀) = 𝐿(𝐶), or is it true that for every circuit ensemble 𝐶, there exists a Turing machine 𝑀 such that �...
Noah Carter's user avatar
1 vote
1 answer
46 views

Does there exist some ``partial" universal hashing?

Suppose we have sets $X$ and $Y$, $|X|=m$, $|Y|=n$. $H$ is a universal family of hash functions from $X$ to $Y$. Let $S\subsetneq X$ be a proper subset of $X$. Does there exist some "partial"...
Kagura Hitoha's user avatar
0 votes
1 answer
26 views

P/poly and dyadic oracle

If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with ...
dino-t's user avatar
  • 23
1 vote
1 answer
128 views

How to construct a carry-lookahead adder of the optimal $O(n)$ size

Problem (TL;DR): I'd like to know how to construct a CLA adder that has $O(n)$ size and $O(\log n)$ depth using only fan-in 2 AND gates and XOR gates, as suggested in this answer and this answer. ...
AXX's user avatar
  • 31
0 votes
1 answer
173 views

Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?

Let's say that we have a decision problem $P$. Let's also say that $I_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite. There is a sequence of ...
Alonso Montero's user avatar
0 votes
1 answer
90 views

SAT with every variable occuring exactly once

With the Circuit-SAT problem, I often see the "split" gate (I don't know the official name of it). This gate has a truth table of: $$ \begin{array}{|c |c c|} 0 & 0 & 0\\ 1 & 1 &...
Loic Stoic's user avatar
1 vote
3 answers
228 views

How do you write a logic function to determine if one 2s complement binary number is less than another?

Working on logic design in class, and I'm trying to figure out how to write a specific logic function [and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example] It asks to ...
mrak-p's user avatar
  • 11
0 votes
0 answers
26 views

Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits

I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$ We have $C|_V$ which is ...
Soham Chatterjee's user avatar
2 votes
0 answers
42 views

Quantum search with input as a classical circuit

Grover's algorithm assumes $U_f$ computing a function $f$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $f$ is given. So let's assume a reversible circuit, $C ...
Loic Stoic's user avatar
1 vote
0 answers
20 views

Why is End-Of-The-Line defined in terms of "Arithmetic circuits" instead of "Boolean circuits"

The definition of PPAD (Polynomial parity arguments on directed graphs) revolves around the definition of "End-Of-The-Line" An exponentially large polynomial-depth arithmetic circuit, $f$, ...
Andrew Baker's user avatar
1 vote
1 answer
38 views

Representing classical circuits with quantum gates

Many problems in computer science input boolean circuits to problems. Just as a toy example, let's define the below problem to be called $A$: Given a polynomial depth circuit with $N$ bits of output, ...
Loic Stoic's user avatar
0 votes
1 answer
34 views

"Succinct circuit representation" on Turing machines?

The famous PPAD class revolves around the End-Of-The-Line problem. Basically, it states that you are given two polynomial depth circuits, $P$ and $Q$, which act as "possible previous" and &...
Loic Stoic's user avatar
1 vote
1 answer
71 views

Acyclic boolean circuit (DAG)

If a function f has a while loop or for loop, can I compile this function into an ...
Emison Lu's user avatar
2 votes
0 answers
32 views

Suggestion for tools/libraries for multi-output boolean circuit minimization?

I am interested in the following problem Input: A boolean function F with n boolean inputs and m boolean outputs. Output: A circuit C implementing F such that C has as few gates as possible. The ...
Agnishom Chattopadhyay's user avatar
0 votes
1 answer
56 views

How do I create a circuit based on this truth table? The solution I implemented is not working as expected

I am trying to create a circuit based on this truth table below: can you describe how to make the circuit using only logic gates ...
randomUser786's user avatar
0 votes
1 answer
50 views

Can an arithmetic circuit have multiple outputs?

An arithmetic circuit relates to calculating the value of a polynomial given some inputs. But is it still considered a circuit if the DAG corresponds to the evaluation of multiple polynomials that ...
Thorkil Værge's user avatar
2 votes
1 answer
80 views

Time complexity when implementing uniform family of circuits

It is known that the complexity class P is equivalent to the class of problems decided by polynomial-time uniform familiy of circuits. When stating the complexity of algorithms as this family of ...
Apo's user avatar
  • 121
1 vote
1 answer
75 views

Can Boolean circuits of polylog depth represent all Boolean functions?

Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to ...
zbh2047's user avatar
  • 296
3 votes
1 answer
792 views

Shannon's result that some Boolean functions require exponential circuits

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
Martin Berger's user avatar
1 vote
1 answer
82 views

prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$

I need to prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$. Where CorrectSATSolver $= \{C | C(\varphi) = 1 \iff \varphi$ is satisfiable$\}$. In other words, CorrectSATSolver ...
ORN's user avatar
  • 23
1 vote
1 answer
89 views

How to bound the size of Boolean circuits?

Every function $f\colon \{ 0, 1 \}^n \to \{ 0, 1 \}$ can be computed by a circuit over the standard unbounded fan-in basis $\mathcal{B}_1 = \{ \neg, (\vee^n)_{n \in \mathbb{N}}, (\wedge^n)_{n \in \...
user251130's user avatar
0 votes
0 answers
52 views

Need to define output functions from logic circuit

i was given a this circuit as exam question So we need to define functions g and f. I defined them as $g(x,y,z) = x \oplus y \oplus z$ and $f(x,y,z) = (x \oplus y) \cdot z$. By definition known that ...
David Sergeev's user avatar
0 votes
0 answers
654 views

Logic Gates - 3 Sensors in a Factory

I am studying logic gates and I encountered this problem: A set of three sensors in a factory detects whether the pollution level it is outputting from an incinerator exceeds the safety limit. In ...
Ahmed Magdy's user avatar
1 vote
0 answers
33 views

Circuit class: constant depth, poly-size, bounded fan-in

I'm looking for the name of a certain circuit complexity class. It captures, to me, the idea of "shallow physically feasible circuits". I'm looking for the class of problems with: Constant ...
Alex Meiburg's user avatar
0 votes
0 answers
29 views

How does the circuit depth of a bijective function change if it is optimally rexpressed in terms of larger gates?

Consider a bijective function $f:\{0,1\}^n\rightarrow \{0,1\}^n$. Let $d_k$ be the minimal circuit depth of $f$ when expressed in terms of arbitrary $k$ bit gates (i.e. arbitrary bijective functions ...
Kfir Dolev's user avatar
3 votes
1 answer
68 views

Circuit size of a random two to one function

Consider the set of all possible two-to-one functions that map inputs from $\{0, 1\}^{n}$ (domain) to outputs in $\{0, 1\}^{m}$ (co-domain) and let $m > n$. If I pick a function randomly from this ...
Sid Meier's user avatar
  • 249
1 vote
1 answer
119 views

How do we enumerate every algorithm in the circuit model?

Consider the family of circuits $\{C_n\}_{n\in \mathbb{N}}$ that are big enough to compute every Boolean function for $n$ variables. We can label the nodes in order starting at the inputs and working ...
HiddenBabel's user avatar
3 votes
1 answer
86 views

Expressivity of Polysize Decision Trees

A binary decision tree (DT) is a binary tree whose internal nodes are labelled by boolean variables (with repetitions), and whose leaves are labelled either $0$ or $1$. The size of a decision tree is ...
integrator's user avatar
  • 1,110
0 votes
0 answers
21 views

NC with nearest neighbor gates

Consider a circuit belonging to the class $\text{NC}^i$, as defined here. From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
Sid Meier's user avatar
  • 249
1 vote
1 answer
376 views

Boolean circuit size bounds on the majority function

I am a bit lost in the literature. Is it known whether there is a $o(n \log n)$ size boolean circuit family for the majority function?
acupoftea's user avatar
  • 458
2 votes
1 answer
71 views

Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$

Define the following languages: $$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in }...
Dennis's user avatar
  • 165
0 votes
1 answer
79 views

Algorithm to reduce a Circuit-SAT to NAND-SAT

I am trying to construct an algorithm to reduce OR, AND and NOT gates into NAND-SAT. Can someone give me a hint as to where to start?
Erik Rosolov's user avatar
1 vote
1 answer
35 views

What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Given the following language: $$ L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
Dennis's user avatar
  • 165
4 votes
1 answer
273 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 ...
Adelhart's user avatar
  • 143
0 votes
1 answer
78 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 ...
InfiniteLoop's user avatar
2 votes
1 answer
294 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 ...
Alex May's user avatar
  • 131
1 vote
1 answer
211 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 ...
ShyPerson's user avatar
  • 925

1
2 3 4 5 6