All Questions
9 questions
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
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
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}$ ...
- 747
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
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
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 ...
- 493
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
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
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