All Questions
Tagged with complexity-theory circuits
18 questions
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
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$
- 1,165
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 $...
- 71
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 ...
user35837
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 ...
- 5,400
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 ...
- 161
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
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
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 ...
- 371
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 ...
- 579
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/...
- 61
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 ...
- 49
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
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 ...
- 5,400
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
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
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
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$) ...
user39969