Questions tagged [circuits]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
58 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
706 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
82 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
52 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
39 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
14 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
16 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
14 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
0 votes
1 answer
39 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
0 answers
40 views

Quantum Full Adder

I've been working on Quantum Circuits for a 1.5 months. And firstly i've created Full Adder in Quantum Circuit. And first times i was creating Full Adder with too Qubits. But last week i created ...
Emir's user avatar
  • 1
0 votes
1 answer
24 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
  • 13
1 vote
1 answer
62 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
0 answers
13 views

$NP\subseteq P/poly\implies PH\subseteq P/poly$

We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
Soham Chatterjee's user avatar
0 votes
1 answer
102 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
54 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
112 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
40 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
0 votes
1 answer
26 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
32 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
0 votes
0 answers
36 views

How to convert loop into combinational circuit?

In high-level programming languages, such as C and Python, loop statements such as while and ...
Emison Lu's user avatar
1 vote
1 answer
59 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
1 vote
0 answers
27 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
45 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
47 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
1 vote
1 answer
51 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
  • 111
1 vote
1 answer
47 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
611 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
62 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
52 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
50 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
416 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
28 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
57 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
  • 229
1 vote
1 answer
102 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
77 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
  • 229
1 vote
1 answer
303 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
  • 438
2 votes
1 answer
63 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
68 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
32 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
3 votes
1 answer
203 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
  • 133
0 votes
1 answer
68 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
216 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
182 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
  • 923
2 votes
0 answers
46 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 ...
exfret's user avatar
  • 332
1 vote
1 answer
69 views

What is the comparator circuit?

The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths. What is the comparator gate constituted from? Structurally why is it believed $...
Turbo's user avatar
  • 2,881

1
2 3 4 5 6