Questions tagged [circuits]
A computation model in which the computation is described via circuits of various logic gates.
282
questions
0
votes
3
answers
37
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 ...
- 1
0
votes
0
answers
21
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 ...
- 101
-3
votes
0
answers
25
views
design circuit by proteus
Design a circuit by which 3 4-bit numbers B, A and C are added together according to the control signal S and in
If the calculation result exceeds 15, the LED will be turned on as an output (it is ...
2
votes
0
answers
38
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 ...
- 73
0
votes
0
answers
13
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$, ...
- 39
0
votes
1
answer
15
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, ...
- 73
0
votes
1
answer
19
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 &...
- 73
0
votes
0
answers
25
views
How to convert loop into combinational circuit?
In high-level programming languages, such as C and Python, loop statements such as while and ...
- 11
1
vote
1
answer
38
views
Acyclic boolean circuit (DAG)
If a function f has a while loop or for loop, can I compile this function into an ...
- 11
1
vote
0
answers
23
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 ...
0
votes
1
answer
29
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
...
- 103
0
votes
1
answer
44
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 ...
- 103
1
vote
1
answer
34
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 ...
- 111
0
votes
0
answers
34
views
Circuit Complexity of Permutation
We are here considering permutations of the form $F_2^n \mapsto F_2^n$. I am interested in the $AC^k[2]$ circuit complexity of such functions. What are the upper and lower bounds in this context? Does ...
- 101
1
vote
1
answer
35
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 ...
- 296
3
votes
1
answer
295
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 ...
- 8,258
1
vote
1
answer
61
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 ...
- 23
1
vote
1
answer
34
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 \...
- 83
0
votes
0
answers
49
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 ...
0
votes
0
answers
225
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 ...
- 111
1
vote
0
answers
16
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 ...
- 816
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 ...
3
votes
1
answer
41
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 ...
- 219
1
vote
1
answer
76
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 ...
- 111
2
votes
1
answer
65
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 ...
- 1,110
0
votes
0
answers
20
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, ...
- 219
1
vote
1
answer
187
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?
- 438
2
votes
1
answer
56
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 }...
- 165
0
votes
1
answer
54
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?
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{...
- 165
3
votes
1
answer
106
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 ...
- 133
0
votes
1
answer
55
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 ...
- 101
2
votes
1
answer
145
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 ...
- 131
1
vote
1
answer
151
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 ...
- 820
2
votes
0
answers
39
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 ...
- 332
1
vote
1
answer
63
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 $...
- 2,844
0
votes
0
answers
23
views
What is the depth of comparator circuit required in Gale Shapely and STCONN?
Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721).
What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
- 2,844
2
votes
0
answers
52
views
Comparing PRAM and Circuit Complexity, $NC^i$
I wondered about the following quote from NC (Wikipedia):
$NC^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and ...
- 21
3
votes
1
answer
34
views
Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?
Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table
00 0
01 0
10 0 (*)
11 1
but such that the case (*) is wrong 1/3 of the time, ...
- 33
1
vote
1
answer
67
views
Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
- 2,844
1
vote
1
answer
40
views
Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$
I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates, and the negation is applied only to input variables.
So, assuming we have a ...
- 35
1
vote
1
answer
51
views
How can you convert the depth of a boolean circuit to its size?
I know that the depth of a circuit is the maximal length from an input gate to the output gate of the circuit and its size is its number of gates.
Is there a formula that you can go from depth to size ...
- 35
4
votes
0
answers
55
views
Problems that are easy on boolean formulas but become NP-hard on circuits?
Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input?
...
- 2,450
0
votes
1
answer
46
views
Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?
Let $\mathcal C$ be a circuit of $m=f(n)$ input wires
where every input is taken in the set $\{x_1,x_1',\dots,x_n,x_n'\}$ where $x_n\in\{0,1\}$ and $x_n+x_n'=1$ holds (not all $x_i,x_i'$ necessarily ...
- 17
1
vote
1
answer
134
views
Iterated multiplication of permutation matrices
Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where
$m=\mathit{poly}(n)$
$m=\...
- 17
2
votes
0
answers
76
views
Prove lower bound on boolean circuit
Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$:
$ A = \begin{...
- 65
1
vote
1
answer
58
views
What is uniformity in Boolean circuits exactly?
I have two questions on Kaveh's answer to Definition of uniform boolean circuit :
Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a ...
- 310
1
vote
1
answer
214
views
How to find the reverse of a binary string with simple binary operators?
I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome?
So my approach is to feed the input to a circuit that reverses the input, ie if ...
- 11
1
vote
1
answer
33
views
Circuits and Closure Under Reductions
Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?
Using similar ideas like Cook-Levin (...
- 23
1
vote
2
answers
86
views
Symmetric functions in NC¹
A boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$.
It is known that every boolean function is in $\mathrm{NC}^1$, i.e. there ...
- 13