All Questions
Tagged with complexity-theory circuits
154 questions
3
votes
1
answer
1k
views
Regular Languages in $ \mathsf{\text{}NC^1}$
Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.
To prove the theorem stated above we need some theorems and definitions given below :
Barrington Theorem : A branching ...
1
vote
0
answers
102
views
How many bits we can negate using two/three NOT gates?
How many bits we can negate using two/three NOT gates ?
I am newbie at this subject so I ask for help. It is about circuits.
Edit
After reading link given in comments by @D.W I think that I can ...
1
vote
1
answer
138
views
Boolean circuit with two inputs and advice input is hard-wired
Claim : $\cup_{c,d} $ DTIME$(n^c)/n^d \subseteq$ $P_{poly}$
Proof : if $L$ is decidable by a polynomial-time Turing machine $M$ with access to advice family $\{\alpha_n\}_{n\in \mathbb{N}}$ of size $...
0
votes
1
answer
94
views
Given snapshot and boolean circuit how to compute coNP formula?
Theorem 6.20: If $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$ then $\mathsf{EXP\text{}} = \Sigma_2 ^{p}$.
My attempt : Let $L \in \mathsf{EXP\text{}}$. Then $L$ is computable by an $2^{p(...
4
votes
2
answers
858
views
Function that cannot be computed by a Boolean circuit of size $2^n/2n$
Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a ...
7
votes
1
answer
2k
views
Given a Turing machine , How to construct a efficient boolean circuit?
The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page ...
2
votes
2
answers
152
views
Given a function and its complexity, what is the complexity of its circuit?
For example,
given an element-wise function $f$, with input $x\in\{0,1\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also ...
0
votes
2
answers
3k
views
Adjacency-list to Adjacency matrix in logarithmic space?
Input : Adjacency-list representation of Directed acyclic graph (Boolean circuit). see Complexity theory by Arora and bark, page no- 104
Find : Adjacency matrix representation of DAG (Boolean ...
1
vote
1
answer
342
views
Computing snapshot of Turing machine from previous snapshots in logarithmic space?
To prove that $P \subseteq P_{\ poly}$ [see book by Arora and Barak, chapter 6, page no 105]
Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \{0,1\}^* $ be some input for $M$...
2
votes
1
answer
80
views
$\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?
Now, I have the following conjecture.
$\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$.
However, I am at a loss at ...
1
vote
1
answer
168
views
Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting
Let me define the problems first
Polynomial Identity Testing $(\mathsf{PIT\text{}})$
Given : A polynomial $p$ over some field $\mathbb{F}$.
Decide : Are all coefficients of the monomials of $p$ ...
8
votes
0
answers
91
views
Connections between circuit complexity and Unique Games Conjecture?
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
2
votes
1
answer
71
views
What are the gap functions in the $AC$ hierarchy?
Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of ...
5
votes
3
answers
947
views
Is Green's the best 16-input sorting network so far?
Every paper says that Green's construction is the best 16-input sorting
network as for now.
But why does Wikipedia says: "Size, lower bound: 53"?
I thought "lower bound" meant:"If there exists at ...
2
votes
1
answer
82
views
Checking membership in DFA with fixed length using AC1 circuit?
I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should ...
2
votes
1
answer
341
views
What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates
In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...
5
votes
1
answer
198
views
Amortizing or batching circuit evaluation for many different inputs?
Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k*2^n)$ simply by calculating all the intermediate values ...
1
vote
0
answers
181
views
On power of $P/poly$
(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close?
(2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the ...
2
votes
1
answer
202
views
A function computable using a circuit of size $10s$ but not of size $s$
I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help.
Prove that for every function $s(n)...
1
vote
1
answer
197
views
Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?
Sanjeev Arora and Boaz Barak show the following :
$P/poly = \cup_{c,d} DTIME (n^c)/n^d$
where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$ and runs in $O(n^c)$ ...
1
vote
1
answer
52
views
What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit?
I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant ...
4
votes
1
answer
137
views
On relation between FFT and polynomial multiplication
Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ ...
1
vote
1
answer
95
views
Unconditional arithmetic circuit lower bounds for permanent/determinant
In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) ...
1
vote
0
answers
27
views
Arithmetic problems known to be in TC^{i+1} but not known to be in TC^i
Is there an arithmetic problem that is known to be in $TC^{i+1}$ but not known in $TC^i$ for any $i\geq0$? Concrete examples for $i=0$ would be of most utility however any arithmetic example is fine.
0
votes
1
answer
65
views
*non-uniform* $ACC^0$ and above classes
$NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$.
We do not know if either $NP$ or $P/poly$ is in $ACC^0$.
Suppose every problem in $NP$ can be solved in polynomial time ...
5
votes
1
answer
230
views
Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?
In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which ...
3
votes
1
answer
312
views
How many inputs does the Hadamard gate have?
Look at the diagram in the middle of page 6-3 here,
http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf
I am confused as to how should one think ...
3
votes
1
answer
1k
views
How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?
The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$.
The ...
8
votes
1
answer
3k
views
What is the decidable language in $P/poly$ but not in $P$?
Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
0
votes
0
answers
112
views
2-depth arithmetic circuits and VP vs VNP
the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary:
is this new paper Sums of ...
6
votes
1
answer
330
views
Is there an intuitive proof for the existence of hard functions?
I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by ...
-2
votes
1
answer
591
views
Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility
Given a gate called Nand with the following truth table:
A | B | A Nand B
------------------
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
We can define ...
3
votes
1
answer
385
views
Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$
I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the ...
1
vote
1
answer
152
views
Polynomial Identity Testing Evaluating a polynomial on a circuit
Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...
9
votes
1
answer
2k
views
Combinational Logic Circuits and Theory of Computation
I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation.
I was wondering whether combinational ...
3
votes
1
answer
574
views
What is the relation between arithmetic circuits and straight line programs?
One definition of arithmetic circuits is as follows:
An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$ usually, $X = \{x_1, \dots , x_n\}$) is a directed acyclic ...
1
vote
1
answer
107
views
What complexity class is this ciruit problem?
I'm exploring an algorithm that solves k-SAT. It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds.
Without knowing the runtime, I speculate on how quickly it will ...
3
votes
0
answers
360
views
AC0 and first order logic equivalence
The page on descriptive complexity theory in Wikipedia states the following:
"First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of ...
2
votes
1
answer
84
views
NP-complete problems and sub-expenential sized circuits
If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?
7
votes
1
answer
413
views
Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight
There is a basic result in circuit complexity that says:
There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.
The argument is a simple counting argument on the ...
3
votes
1
answer
143
views
Assume that SAT ∈ PSIZE, does it imply that NP = coNP?
Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ?
I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ ...
2
votes
1
answer
394
views
Computing parity function on n variables with O(n) gates
Sipser example 9.29
He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same ...
5
votes
1
answer
255
views
Modulo operation in monotone complexity
Given $x\in\Bbb N$, I would like to find $x\bmod N$, where $N$ is composite. For example $N=35$, $x=53$ and $x\bmod N=18$. Is this operation considered monotone in circuit/algebraic complexity ...
4
votes
0
answers
472
views
PARITY using depth one TC0 circuit
I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a ...
7
votes
1
answer
416
views
How to relate circuit size to the running time of Turing machine
From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/,
Define, $M_{[x,c]}$ as the deterministic Turing machine that operates
as follows on an input $y$. The machine treats $...
4
votes
2
answers
2k
views
Definition of uniform boolean circuit
Definition
A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log
space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/...
2
votes
2
answers
524
views
What does "number of gates" mean in circuit complexity?
By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.
6
votes
2
answers
2k
views
Formulas vs Circuits
In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A ...
5
votes
1
answer
269
views
Simple lower bounds against AC0
It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \...
12
votes
1
answer
433
views
Which non-regular languages are in $AC^0$?
For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.