7
$\begingroup$

It is well known that lower bounds on circuits implies lower bounds on time complexity, just because circuits can efficiently simulate algorithms.

By the continuous work started by Ryan Williams, we know that upper bounds on the algorithms can imply circuit lower bounds [1].

Another connection between uniform and non-uniform complexities is that there exist algorithms that uses efficient circuits to gain a speed up. For example, first subquadratic algorithm for 3-sum [2] uses efficient decision trees.

I'm looking for results in the direction I haven't discussed yet: can lower bounds for time complexity imply lower bounds for circuit complexity. It is worth mentioning that algorithms that uses efficient circuits are taking advantage of the actual constructions rather then pure existence.

[1] Improving exhaustive search implies superpolynomial lower bounds. Ryan Williams.

[2]Threesomes, Degenerates, and Love Triangles. Allan Grønlund, Seth Pettie

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ P/poly has undecidable problems, so ​ ​ ​ NEXP $\subseteq$ P/poly ​ $\implies$ ​ NEXP $\subset$ P/poly ​ $\implies$ $\hspace{1.09 in}$ NEXP = MA $\subseteq$ PSPACE $\subseteq$ EXP ​ , ​ ​ ​ so by contrapositive, if ​ NEXP $\not\subseteq$ EXP ​ then ​ NEXP $\not\subseteq$ P/poly . $\hspace{.63 in}$ $\endgroup$
    – user6973
    Apr 11, 2017 at 22:58
  • 4
    $\begingroup$ By Karp-Lipton theorem, if $NP \subseteq P/poly$ then $\Sigma_2 = \Pi_2$. Thus, a lower bound that shows that $\Sigma_2 \ne \Pi_2$ would imply $NP \not\subseteq P/poly$. $\endgroup$
    – Or Meir
    Apr 11, 2017 at 23:24
  • $\begingroup$ @OrMeir: Those are two great examples, which seem like perfectly good answers! $\endgroup$
    – Joshua Grochow
    Apr 12, 2017 at 3:01
  • $\begingroup$ In general, Karp-Lipton-type theorems have the form: "circuit upper bound implies uniform upper bound" ... although I have the feeling Ivan meant something more concrete, where a time lower bound for a problem $\Pi$ implies a circuit lower bound for the same problem $\Pi$. Even so, NEXP != EXP implies NEXP not in P/poly is pretty solid! $\endgroup$
    – Ryan Williams
    Apr 12, 2017 at 3:37
  • $\begingroup$ Those are really good examples! Indeed I would rather have an example of lower bound transfer from uniform world to non-uniform for the same problem, but this is close enough. $\endgroup$
    – ivmihajlin
    Apr 12, 2017 at 5:33

1 Answer 1

Reset to default
3
$\begingroup$

MA $\subseteq$ PSPACE $\subseteq$ EXP $\subseteq$ NEXP ​ and ​ P/poly has undecidable unary languages, so
NEXP $\subseteq$ P/poly ​ $\implies$ ​ NEXP $\subset$ P/poly ​ $\implies$ ​ NEXP $\subseteq$ EXP .


As something like a generalization of that ​ (showing that EXP-complete languages are
in CHECK is difficult) , ​ for all languages L in CHECK with a checker whose queries all have
length at most ​ nd , ​ for all non-decreasing functions ​ S : {0,1,2,3,4,...} $\to$ {0,1,2,3,4,...} :

If L's circuit-size in bits is at most S then
L ​ $\in$ ​ DSPACE$\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}n^d\hspace{-0.05 in}\cdot \hspace{-0.03 in}S\hspace{-0.05 in}\left(\hspace{-0.03 in}n^d\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.04 in}+\hspace{-0.03 in}poly\hspace{.02 in}(n)\hspace{-0.03 in}\right)$ ​ $\subseteq$ ​ DTIME$\hspace{-0.02 in}\left(\hspace{-0.05 in}2^{\left(n^{\hspace{.02 in}d} \hspace{-0.02 in}\cdot S\left(\hspace{-0.02 in}n^{\hspace{.02 in}d}\hspace{-0.03 in}\right)\hspace{-0.03 in}\right)+\hspace{.02 in}poly\hspace{.02 in}(n)}\hspace{-0.04 in}\right)$ ​ ​ ,
so by contrapositive, if ​ ​ ​ L ​ $\not\in$ ​ DTIME$\hspace{-0.02 in}\left(\hspace{-0.05 in}2^{\left(n^{\hspace{.02 in}d} \hspace{-0.02 in}\cdot S\left(\hspace{-0.02 in}n^{\hspace{.02 in}d}\hspace{-0.03 in}\right)\hspace{-0.03 in}\right)+\hspace{.02 in}poly\hspace{.02 in}(n)}\hspace{-0.04 in}\right)$
then L's circuit-size in bits exceeds S infinitely-often.


("in bits" as as opposed to "in gates".)


Similarly, for all functions T and $\ell$ and $S$ from {0,1,2,3,...} to {1,2,3,4,5,...},
for all search problems R in ​ FNTIME(T) ​ whose output-lengths are bounded above by $\ell$:

If R's circuit-size in bits is at most S then R is solvable by ​ FDTIME$\left(\hspace{-0.02 in}2^{S(n)} \hspace{-0.04 in}\cdot \hspace{-0.04 in}poly\hspace{.02 in}(S(n))\hspace{-0.04 in}\cdot \hspace{-0.04 in}T(n)\hspace{-0.03 in}\right)$ ,
so by contrapositive, if R is not solvable by ​ FDTIME$\left(\hspace{-0.02 in}2^{S(n)} \hspace{-0.03 in}\cdot \hspace{-0.03 in}\left(\left(\hspace{.05 in}poly\hspace{.02 in}(S(n)) \cdot \ell(n)\right)+ T(n)\right)\hspace{-0.03 in}\right)$
then R's circuit-size in bits exceeds S infinitely-often.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.