Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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 $...
Complexity's user avatar
  • 1,205
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(...
user avatar
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 ...
Kate's user avatar
  • 49
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 ...
user avatar
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 ...
xtt's user avatar
  • 739
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 ...
user avatar
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$...
user avatar
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 ...
Alex's user avatar
  • 121
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$ ...
user avatar
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 $\...
Andrew's user avatar
  • 286
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 ...
gradstudent's user avatar
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 ...
Christian Pao.'s user avatar
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 ...
Armin's user avatar
  • 29
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 ...
user53733's user avatar
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 ...
mcdowella's user avatar
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 ...
Turbo's user avatar
  • 2,919
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)...
Evgeny A.'s user avatar
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)$ ...
advocateofnone's user avatar
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 ...
user13987's user avatar
  • 113
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$ ...
user avatar
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$) ...
user avatar
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.
Turbo's user avatar
  • 2,919
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 ...
Turbo's user avatar
  • 2,919
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 ...
Turbo's user avatar
  • 2,919
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 ...
user6818's user avatar
  • 1,165
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 ...
Thomas Klimpel's user avatar
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$
user6818's user avatar
  • 1,165
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 ...
vzn's user avatar
  • 11.1k
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 ...
user6818's user avatar
  • 1,165
-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 ...
mike10101's user avatar
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 ...
iHubble's user avatar
  • 207
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 ...
Gaganpreet's user avatar
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 ...
nerdy's user avatar
  • 371
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 ...
Thomas Klimpel's user avatar
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 ...
Matt Groff's user avatar
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 ...
user13675's user avatar
  • 1,664
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?
user10101's user avatar
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 ...
GMB's user avatar
  • 579
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}$ ...
Robert777's user avatar
  • 747
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 ...
lars's user avatar
  • 483
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 ...
Turbo's user avatar
  • 2,919
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 ...
vikraman's user avatar
  • 173
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 $...
circuit's user avatar
  • 71
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/...
TPR's user avatar
  • 61
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.
TPR's user avatar
  • 61
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 ...
bromut's user avatar
  • 61
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 \...
sdcvvc's user avatar
  • 3,501
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.
Alex Grilo's user avatar