All Questions
Tagged with complexity circuit-complexity
6 questions
-1
votes
1
answer
264
views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
- 13.3k
16
votes
0
answers
281
views
Does small circuits for a NP-complete problem contradict ETH?
The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
- 161
5
votes
1
answer
248
views
Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders
Let $X={x_1,...,x_n}$ be a set of variables and $\pi:[n]\rightarrow [n]$ be a permutation of the $n$-element set $[n]=\{1,...,n\}$.
A $\pi$-OBDD is an oblivious, read-once branching program where ...
- 1,072
13
votes
2
answers
524
views
Collapses under the assumption that $NEXP\subseteq P/Poly$
It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$.
What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?
- 696
14
votes
3
answers
1k
views
P/Poly vs Uniform Complexity Classes
It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization.
What is the smallest uniform class C for which one can ...
- 696
2
votes
0
answers
229
views
Circuit complexity lower bounds and uniformity
I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.
For example, the word problem for ...
- 31