13
$\begingroup$

Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$.

On the other hand, it might be that we have much smaller uniform circuits for that problem, even if $t(n)$ is an optimal running time. The circuits may take longer than $t(n)$ to generate, but they are small.

But do we actually know how to build such things? I think the initial question to ask is

(1) Do we have any constructive examples of nontrivial uniform circuits, i.e. uniform circuits whose size is smaller than the best-known running time of any algorithm for the same problem?

Now, I believe that if a problem is in $\mathsf{DTIME(t(n))}$, then we have an exponential-time algorithm to find optimal circuits using an exhaustive search: Given $n$, we write down the answers on all $2^n$ inputs (taking time $(2^n)t(n)$); then we enumerate all circuits on $n$ inputs in increasing size until one is found that gives all the correct answers. The search terminates at either the size of the trivial conversion, $t(n) \log t(n)$, or the truth table of the function, $2^n$ if outputs are $\{0,1\}$. (Edit: Thomas points out that the bound is $O(2^n/n)$ due to Shannon/Lupanov.)

So we have an unsatisfactory "yes" to question (1): Take a language that is hard for any time above $2^n$, but still decidable; the above procedure outputs a truth table of size $2^n$.

So we should refine question (1). I think the two most interesting cases are

(2) Do we have any constructive examples of polynomial-size nontrivial uniform circuits? (Even if they are generated by very slow algorithms.)

(3) Do we have any constructive examples of polynomial-time generatable, polynomial-size nontrivial uniform circuits?

This may be too much to ask. How about an easier question: Do we even know that such a thing is possible? Perhaps no nontrivial uniform circuits exist?

(4) Is the following statement known to be false for any $s(n) = o(2^n)$? (Edit: $o(2^n/n)$, thanks Thomas.) "If a language $L$ has uniform circuits of size $O(s(n))$, then it also has algorithms running in time $\tilde{O}(s(n))$." (If so, then what about when "uniform" is replaced with "polynomial-time-uniform", "logspace uniform", etc?)

Finally, if the above questions are too hard,

(5) Do we have any constructions of uniform families of circuits that are not simply conversions of algorithms into circuits (or writing down the truth table)?

Postscript. An expert I asked about this mentioned "On Medium-Uniformity and Circuit Lower Bounds" (pdf), Santhanam and Williams 2013, which maybe is the most closely related work, but it proves lower bounds (that poly-time-generatable circuits are not too powerful). I'd be interested in any other related work!

$\endgroup$
  • $\begingroup$ 1,2,3,4: Identity function. 5. it is not clear to me what you mean by "being a conversion of algorithms into circuits", we can always convert a uniform circuit into a Turing machine (with a small overhead). $\endgroup$ – Kaveh Jun 6 '14 at 9:25
  • $\begingroup$ @Kaveh, re #5: Good point, but I guess what I have in mind is someone writing down an explicit construction of uniform circuits, that does not look like "convert this TM into a circuit". Also, I think the conversion you mention might not really mean that the circuit "looks like" an algorithm. E.g, say we have a size-$n$ circuit that takes $n^3$ time to generate. We can turn it into a time-$n^3$ TM, ok, but it doesn't resemble the circuit very much, and the naive conversion of that TM back into a circuit is now of size ~ $n^3$. I hope this shows why the question interests me. $\endgroup$ – usul Jun 6 '14 at 12:42
  • 1
    $\begingroup$ @Kaveh: How does the identity function answer 1-4? $\endgroup$ – Joshua Grochow Jun 6 '14 at 16:34
  • $\begingroup$ @Joshua, we can directly describea a uniform circuit of (wire) size O(n), which is better than the conversion of the Turing machine for identity to a circuit. $\endgroup$ – Kaveh Jun 6 '14 at 20:44
  • $\begingroup$ My point is there are important small details the we need to care about to make the question answerable. Another example: BPP is in P/poly and the conversion is computable. If the circuit generation is done by an efficient algorithm combining it with circuit value will give an efficient TM. Conceptually the circuit and the TM compute the same algorithm. The fact that size and time may not correspond exactly is normal, they are defined for different computation models and we know they don't correspond. Arguably time corresponds more to depth than to size. $\endgroup$ – Kaveh Jun 6 '14 at 21:05
8
$\begingroup$

Here are answers to your last two questions.

(5) Sorting networks are uniform circuits that sort as fast as the best RAM algorithms, but are definitely not just conversions of RAM algorithms (e.g. quicksort). [AKS83,G14]

(4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon>0$, but for a silly reason: Every function is computed by a circuit of size $(1+o(1)) \cdot 2^n/n$. (Shannon proved this up to a constant and Lupanov got the optimal constant.) By the time hierarchy theorem, there exists a function $f$ with uniform time complexity between $\Omega(3^n)$ and $O(n \cdot 3^n)$. This gives a counterexample: $f$ has circuits of size $O(2^n/n)$ (which I think are computable in $2^{\mathrm{poly}(n)}$ time) but is not computable in $\tilde{O}(2^n/n)$ time. You should probably ask for $s(n) = o(2^n/n)$.

This is an interesting question; I hope someone can answer (1)-(3).

$\endgroup$
  • $\begingroup$ Thanks, you're right, I intuitively wanted to rule out this "upper-bounding" case but didn't know the right asymptotic. I've edited the question to include that case. $\endgroup$ – usul Jun 7 '14 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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