All Questions
Tagged with complexity-theory circuits
154 questions
1
vote
2
answers
272
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 ...
user172436
1
vote
0
answers
32
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^...
- 111
2
votes
1
answer
121
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 ...
- 221
4
votes
0
answers
42
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(...
- 141
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 ...
- 2,041
0
votes
1
answer
171
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 ...
0
votes
1
answer
55
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 ...
- 103
0
votes
0
answers
44
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 ...
- 11
1
vote
1
answer
48
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"...
0
votes
1
answer
28
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 ...
- 23
0
votes
1
answer
191
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 ...
- 145
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 ...
- 145
2
votes
1
answer
106
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 ...
- 121
3
votes
1
answer
907
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,358
1
vote
1
answer
83
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
0
votes
0
answers
31
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
69
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 ...
- 249
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, ...
- 249
2
votes
1
answer
72
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
1
vote
1
answer
37
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
4
votes
1
answer
291
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 ...
- 143
2
votes
1
answer
357
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
217
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 ...
- 947
2
votes
0
answers
58
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 ...
- 352
1
vote
1
answer
78
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,919
0
votes
0
answers
27
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,919
2
votes
0
answers
77
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
1
vote
1
answer
84
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,919
4
votes
0
answers
64
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,511
1
vote
1
answer
164
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
93
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{...
- 105
1
vote
1
answer
109
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 ...
- 320
1
vote
1
answer
59
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
122
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
2
votes
1
answer
120
views
Closure properties of Alternating Circuit 1 level
Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.
Is this class closed under Kleene star?
I thought it would be simple since it is ...
user129648
1
vote
0
answers
39
views
Converse of Impagliazzo, Kabanets, Wigderson
I am trying to prove that $\text{NEXP} = \text{MA} \Rightarrow \text{NEXP} \subseteq P/\text{Poly}$. I tried to approach the result via trying out the contrapositive, that $\text{NEXP} \nsubseteq P/\...
- 246
1
vote
1
answer
48
views
Functions with small support have small circuits
I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:
Show that if a function $f\colon \{0,1\}^n→\...
- 13
-1
votes
1
answer
45
views
single circuit simulating multiple Turing machines
You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?
- 375
0
votes
0
answers
21
views
Simulation of circuits with circuits
From classical results of universal simulation of Turing machines there exists a Universal Turing machine simulating any Turing machine with time complexity 𝑇(𝑛) in time 𝑇(𝑛)log𝑇(𝑛).
Is there is ...
- 375
1
vote
1
answer
152
views
Connection between Pseudo random generators and hardness
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
- 246
3
votes
0
answers
111
views
Circuit complexity of hardest monotone function
Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such
that the minimal size of a monotone circuit that computes $f$ is
$\Omega(2^n / n^2)$. Use the fact that the number of ...
- 163
1
vote
2
answers
68
views
Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n
Here is a question from Computational Complexity by Arora and Barak:
Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$.
(...
- 246
1
vote
0
answers
61
views
Why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, $p$ and $q$ prime
I am going through Computational Complexity by Arora and Barak, and there I came across the proof of why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, where $p$ and $q$ are distinct primes. ...
- 246
3
votes
1
answer
101
views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
- 33
1
vote
1
answer
148
views
What is the difference between SIZE(n^k) and P/poly?
What is the difference between $\text{SIZE}(n^k)$ and $\text{P}/\text{poly}$?
For reference:
$\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with ...
user122281
4
votes
1
answer
71
views
Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k?
Traditionally, the $W$ hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class $W[t]$ is defined as the closure under $\mathrm{fpt}$-reductions of the ...
- 1,281
2
votes
2
answers
265
views
Construct a Circuit computing all boolean functions over n bits
Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all
distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ ...
1
vote
2
answers
595
views
Proof that uniform circuit families can efficiently simulate a Turing Machine
Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity ...
- 11
2
votes
0
answers
275
views
Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
- 221
2
votes
1
answer
122
views
Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
- 221