Questions tagged [circuits]
A computation model in which the computation is described via circuits of various logic gates.
303 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
0
answers
79
views
What is the smallest algebraic circuit to compute product of a vector by a fixed square matrix?
Given a fixed $n \times n $ square matrix $M$ over a field of size $ \Omega(n^2) $.
What is the size $s_M$ of the smallest circuit that computes the function $f(x)= Mx$ ?
What is the largest $s_M$ ...
0
votes
1
answer
203
views
What could a neat circuit using full adders implementing selectable arithmetic operations on two 3-bit inputs look like?
In a quiz on computer organization, we were asked the following question:
Design an arithmetic circuit that has two selection variables ( $\mathrm{S}_0$ and $\mathrm{S}_1$ ), and two 3-bit inputs ($A$...
user avatar
user163790
0
votes
1
answer
82
views
Question regarding relation between NP and non-deterministic NC1
Let $L$ be an arbitrary language in $NP$. Then,
For every input length $n$ we have a non-deterministic CNF formula for $L,ドル by the Cook-Levin theorem.
Every polynomial-sized formula can be converted ...
0
votes
0
answers
94
views
Why is a 'Clock' Used in Computers?
To clarify, this is not a formal academic field of study for me. At around the timestamp of 11:10 in this video (https://youtu.be/I0-izyq6q5s?si=xQ6Ec2RvZuJm67tl), I find myself wondering why an ...
1
vote
0
answers
55
views
Pairwise (partial) equivalence of boolean functions [closed]
I have a bunch of boolean functions, say $b_1,b_2,\dots,b_k \colon \{0,1\}^m \to \{0,1\}^n,ドル all given in terms of circuits.
I want to determine for which inputs they pairwise agree, that is, I want ...
1
vote
2
answers
332
views
Boolean circuits with fan-out of each gate is 2
I am following the book of Arora and Barak book.
We consider Boolean circuits as we do, Specifically, inner nodes are either AND, OR (both – fan-in 2), or NOT (fan-in 1) gates. The fan-out of each ...
user avatar
user172436
2
votes
0
answers
124
views
How might a fuzzy logic rice cooker actually use fuzzy logic?
This rice cooker purports to use Advanced Fuzzy Logic.
I understand it's hard to know how this specific rice cooker works, so my question is how might fuzzy logic for a rice cooker work in general? ...
1
vote
0
answers
83
views
Depth of circuit computing f(x) = "first n bit string with circuit complexity sqrt(n)"
I want to construct a depth $\mathrm{poly}(n)$ circuit computing $$f(x) = \text{first }n\text{ bit string with circuit complexity }\sqrt n$$ where $x \in \{0, 1\}^n$. I see how to do it with depth 2ドル^...
0
votes
1
answer
106
views
Do computers have an optimal circuit for 64bit addition?
Addition is implemented in computers using a circuit of logic gates.
Do we know what is the lowest depth circuit possible for 64bits?
And is it used in practice?
1
vote
2
answers
567
views
How do logic gates handle if-else statements?
There are questions here and on electrical engeneering stackexchange with similar titles, but they do not quite address the part that is bugging me. I hope I can explain it here in a clear way and ...
4
votes
1
answer
2k
views
Why can't we prove SAT is NP complete just using the Tseytin Transformation?
The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine.
I am confused as to why just the Tseytin Transformation does not imply/prove ...
2
votes
1
answer
158
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 ...
4
votes
0
answers
67
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(...
1
vote
2
answers
346
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 ...
1
vote
2
answers
225
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?