Questions tagged [circuit-complexity]
The circuit-complexity tag has no summary.
15 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
0
answers
125
views
Open Problem: Structural Learnability of Pseudo-Random Boolean Circuits
I would like to propose an open problem at the intersection of computational complexity, pseudorandomness, and circuit theory. This problem has potential implications for cryptography, AI model ...
1
vote
0
answers
77
views
Understanding Reversibility of Quantum Computing in Proving Boolean Circuits as A Subcase of Quantum Circuits
I'm reading quantum computation in Arora and Barak, on page 215 they provide the Lemma 10.10 proving that quantum circuits can simulate boolean circuits.
Lemma 10.10 (Boolean circuits as a subcase of ...
0
votes
1
answer
68
views
Relationship between Formula Complexity and Depth Complexity of A Boolean Function
A (de Morgan) formula $\phi$ is a rooted binary tree, whose leaves are identified with
literals of the forms $x_i$ and $\neg x_i,ドル and whose internal vertices are labeled as AND ($\land$) or OR ($\lor$...
2
votes
1
answer
65
views
Convert the language into CNF or DNF form
A boolean circuit C has n inputs and m outputs, and is constructed with AND, OR, and NOT gates. Each gate has fan-in 2 except the NOT gate which has fan-in 1. The out-degree can be any number. A ...
0
votes
0
answers
70
views
Boolean circuit with true value
Let
$$L=\left\{,円\langle,円B_n,,円 ,円x,円\rangle:\enspace\substack{B_n \text{ is a boolean circuit and }
\\x \in \{0, 1\}^n\text{such that }B_n(x) = 1}\right\}$$
I want to prove that $L$ is $\textbf{P}$-...
1
vote
1
answer
179
views
Whether $\textbf{PH}$ collapses to $\Sigma^p_1$ when $\overline{3SAT}\in \textbf{BP$\cdot$NP}$
I'm doing ex. 7.8 in Arora and Barak
Show that if $\overline{3SAT}\in \textbf{BP$\cdot$NP},ドル then $\textbf{PH}$ collapses to $\Sigma_3^p$.
This is definition of $\textbf{NP}/poly$:
A ...
1
vote
0
answers
60
views
Prove that $\textbf{NC}$ circuit family can compute log space reduction
Most proofs of the problem that I have seen stop at proving $\textbf{NL}\subseteq \textbf{NC}^2$ and not explicitly point out the circuit. I'm trying to show that $\textbf{NC}$ circuit family can ...
1
vote
1
answer
108
views
Confusing on the proof $\textbf{NC}^1\subseteq \textbf{L}$ using DFS
On page 430 of Sisper's TOC, Theorem 10.39 proves $\textbf{NC}^1\subseteq \textbf{L}$:
PROOF: We sketch a log space algorithm to decide a language $A$ in $\textbf{NC}^1$ . On
input $w$ of length $n,ドル ...
2
votes
1
answer
96
views
Are classes $\textbf{NC}$ and uniform $\textbf{NC}$ the same?
On page 117 in Arora and Barak, the definition of class $\textbf{NC}$:
For every $d,ドル a language $L$ is in $\textbf{NC}^d$ if $L$ can be decided
by a family of circuits $\{C_n\}$ where $C_n$ has poly(...
1
vote
2
answers
322
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
0
votes
1
answer
102
views
Is it possible there exists a reduction that satisfies conditions of reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}?$
I am following the Barak and Arora book. I have asked this question regarding reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}.$
Is it possible to show that there exists a reduction that satisfies ...
user avatar
user172436
1
vote
1
answer
110
views
Reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$
I am following the Barak and Arora book, in circuit chapter, they use direct reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$ directly without any clue.
How to construct an explicit reduction ...
user avatar
user172436
5
votes
1
answer
77
views
Citation/ Proof of a theorem in computational complexity about recursive majority
Circuit Depth Lower Bound for Iterated Majority Function
Let $k \geq 3$ be a fixed integer. The function computed by a balanced $k$-ary tree of depth $d(n) = \Theta(\log n),ドル where each node computes ...
1
vote
0
answers
49
views
DLOGTIME sequential access (uniformity conditions for circuits)
Consider the direct connection language of a circuit family, consisting of tuples (a,p,b,y) where
a is a gate number
p a binary string is an encoding for a predecessor or type
b is a gate type or ...
1
vote
0
answers
88
views
What are the shortest circuits to sum bits?
I am interested in circuits that reduce 2ドル^n-1$ input bits into their sum, represented as an $n$ bit integers. For $n=2,ドル this is a full adder, which can be implemented with 5 gates of 2 inputs in ...