All Questions
Tagged with circuits complexity-theory
154 questions
1
vote
0
answers
21
views
Boolean circuit multigraph
Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer].
He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some ...
- 143
2
votes
0
answers
101
views
Are minimum boolean circuit sizes for small problem sizes of an NP-complete problem known?
I think that a table with the following numeric values would be very interesting, but I could not find any table online displaying them:
Choose any NP-complete problem (say, clique, but a problem ...
- 113
1
vote
1
answer
89
views
Relationship between circuit size and formula size in Sipser text
The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can ...
- 947
2
votes
0
answers
89
views
Class of languages recognizable by n-bit formulas of size at most $T(n)$
A 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 nodes
fan-...
- 221
4
votes
0
answers
176
views
Circuit complexity of random Boolean functions
I just saw a YouTube video where Ryan Williams gives a talk about circuit complexity. He stated that random Boolean functions require exponential size circuits to compute, but I don't understand why ...
1
vote
1
answer
123
views
What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?
If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
- 111
5
votes
1
answer
106
views
How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?
In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies ...
- 5,037
2
votes
0
answers
60
views
Does Cook and Ruzzo's result also hold for logspace-uniform AC0?
In Cook's famous paper on $\mathsf{NC}$, he cites the following result:
PROPOSITION 4.7 (Cook and Ruzzo, 1983). $\mathsf{AC}^k$ consists of those
problems solvable by uniform unbounded fan-in ...
- 5,037
1
vote
1
answer
105
views
Polysize bounded depth circuit for modified MAJORITY problem
I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 -...
- 161
1
vote
1
answer
282
views
How to show that the product of two binary numbers can be determined in AC1?
I was working on a proof to determine that a product cannot be done in AC0, how can a proof that can be done in AC1?
- 101
0
votes
0
answers
52
views
Boolean circuit size of $i$th bit of determinant?
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers.
Is there a polynomial size boolean circuit for $i$th bit of ...
- 2,919
1
vote
1
answer
57
views
Logical characterization of $NC^1$
Morioka in his 2005 dissertation [1] referenced "On Uniformity within $NC^1$" by
Barrington, Immerman, and Straubing. Using the following statement:
Every $\mathbf{NC^1}$-predicate is computed by ...
- 125
1
vote
2
answers
350
views
Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?
Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?
- 53
2
votes
1
answer
85
views
Programs to circuit conversion
Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME[f(n)]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates?
How about when ...
- 2,919
2
votes
1
answer
86
views
Satisfiability Toward A Sequential Circuit
Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean ...
- 271
2
votes
0
answers
224
views
Implementing depth-3 circuit for XOR
In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR.
I tried for a little bit to figure out how to do this, but couldn't find ...
- 21
18
votes
1
answer
2k
views
Why aren't P and P/poly trivially the same?
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
- 291
1
vote
0
answers
52
views
Best-known Boolean Circuits for Clique? [closed]
Not having received a satisfactory response to this question in math.SE, I am asking it here:
In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
- 947
1
vote
1
answer
136
views
Smallest circuit for square of sparse symmetric matrix
I have an $n \times n$ symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are $\sqrt{n}$ nonzero entries in each row/column, so ...
- 955
0
votes
0
answers
55
views
Is the succinct version of P-complete problems out of P?
Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
- 83
0
votes
0
answers
33
views
Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits
I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is ...
- 597
4
votes
1
answer
694
views
Circuits vs Turing Machines in the "nonuniform model of computation"
I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the ...
- 597
0
votes
1
answer
76
views
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
- 55
1
vote
0
answers
43
views
Introduction to circuit complexity? [closed]
The books I'm reading on complexity theory primarily are about complexity of decision problems by Turing machines.
I'm interested in computational complexity of circuits, both boolean and continuous ...
- 277
2
votes
2
answers
384
views
Circuit satisfiability problem : SAT-C to SAT-2C
I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C.
Prove that ...
- 43
1
vote
0
answers
56
views
projection of arithmetic formulas to determinant
I am looking for a direct proof (i.e. without going through ABPs) that if $f(\bar{x})$ has an arithmetic formula of size $s$ then it is a projection of an $O(s)\times O(s)$ determinant.
It seems ...
- 752
3
votes
1
answer
188
views
Is it known that $AC^1 \subseteq L$?
A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
- 7,248
4
votes
1
answer
272
views
Simple example of exponential gap between monotone and non-monotone circuits
Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone ...
D.W.♦
- 166k
2
votes
1
answer
514
views
Space complexity of boolean circuit evaluation
I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size.
Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$.
Now, assuming the fan in of ...
- 193
1
vote
1
answer
195
views
Why does the ouput of an NC0 circuit depend on only a constant number of input bits?
I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, ...
- 21
6
votes
1
answer
709
views
Proving that EXP doesn't have polynomial-size circuits
How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$?
I have a reminder that says
$$ \mathrm{EXP} =\...
- 61
1
vote
1
answer
224
views
On importance of Stockmeyer theorem
Theorem: (Stockmeyer, 1974) Any circuit that takes as input a formula
(in the language of WS1S) with up to 616 symbols and produces as
output a correct answer saying whether the formula is valid ...
- 484
1
vote
0
answers
41
views
About sign-rank of Boolean functions
Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
- 493
2
votes
0
answers
40
views
From SETH to circuit lowerbounds
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)
In threshold ...
- 493
0
votes
0
answers
46
views
Circuit Lower bound for $EXP^{NP}$
By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.
Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).
By using the ...
- 393
2
votes
1
answer
245
views
Containment of ACC$^0$ in TC$^0$
The Complexity Zoo states that ACC$^0$ is contained in TC$^0$ and links to the paper On ACC and Threshold Circuits. However, what the linked paper proves is that depth-3 threshold circuits of ...
2
votes
1
answer
118
views
$ACC^{0}$ vs Poly-size circuits of bounded degree
We know that NEXP $\not\subset ACC^0$ (Ryan Williams'10 Result). Also, We know that even $\Sigma_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ (Kannan'...
- 393
4
votes
2
answers
606
views
NP-hardness of MCSP
Ryan Williams and Cody Murray in 2015 proved that MCSP (Minimum Circuit Size Problem) is provably not NP-hard under local reductions. (Local reductions are the ones in which you are allowed time $O(n^{...
- 393
0
votes
1
answer
122
views
LTF circuits and $AC^0$
Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).
For any vector $w \in \mathbb{R}^n$ and any number $c \in \...
- 493
0
votes
1
answer
33
views
Taking mod $2$ with LTF gates
Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?
I do not mean that the ...
- 493
9
votes
1
answer
2k
views
How to show that hard-to-compute Boolean functions exist?
How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute?
This problem was originally stated in Exercise 3.16 of Nielsen & ...
- 223
-1
votes
1
answer
43
views
Some questions about the depth hierarchy of threshold circuits
Let me split my query into a few parts which possibly have overlapping answers,
How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) ...
- 493
1
vote
2
answers
498
views
Show that boring boolean circuit belongs to NP-complete class
We say that a boolean circuit is boring if it returns the same
result for $>\frac34$ possible input, where we have $n$ input gates.
Hence, boring circuit returns the same output ($0$ or $1$) ...
- 379
1
vote
1
answer
370
views
Show that problem is PSPACE-complete - path in directed graph
I have a following problem:
Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...
- 379
5
votes
1
answer
192
views
Lower bound of degree of polynomial approximating parity
Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$
It is known [See e.g. Lemma 5 of this lecture note] that any ...
- 283
2
votes
1
answer
87
views
small size and small depth circuit for set intersections
Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$.
Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then ...
- 21
0
votes
1
answer
65
views
boolean circuit to decide if there's a path of at most $k$ edges from $u$ to $v$ in graph $G$
Let an undirected graph and $k\in\mathbb{N}$. Prove that there's a circuit of depth $2$, size of $n^{O(k)}$ and unlimited fan-in, which gets $\langle G,v,u\rangle$ as an input and checks if there's a ...
- 25
1
vote
1
answer
116
views
$L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$
Prove that $L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$.
I managed to prove the $(\impliedby)$ and I want to prove $(\implies)$.
I feel that we need to take the ...
- 752
2
votes
1
answer
458
views
Why each function may be computed with circuit with 2^n gates?
Why each function may be computed with circuit with 2^n gates ?
I am trying to understand this thing, but I can't. In particular why function constant $1$ requires $2^n$ gates. For me, it should be ...
user54001
1
vote
1
answer
106
views
How can languages that are E-complete have sub-exponential size circuits?
The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta > 0$ is open, and this would imply some derandomization results.
...
- 517