13

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!

Community
  • 1
usul
  • 7,615
  • 1
  • 26
  • 45
  • 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). – Kaveh Jun 06 '14 at 09:25
  • @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. – usul Jun 06 '14 at 12:42
  • 1
    @Kaveh: How does the identity function answer 1-4? – Joshua Grochow Jun 06 '14 at 16:34
  • @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. – Kaveh Jun 06 '14 at 20:44
  • 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. – Kaveh Jun 06 '14 at 21:05
  • too many questions, suggest splitting them... agreed with K.s challenge. uniform circuits and TM lower bounds are basically interchangeable within exactly or nearly constant factors (ie big-Oh bounds), right? so the question about uniform circuits seems somewhat superfluous, it might as well just ask about any lower bounds (afaik no unrestricted/nonuniform lower bounds have ever been proven lower than uniform bounds, right?). the questions also seem to miss connection between proofs/algorithms, re Curry-Howard correspondence there exist no proofs that cannot be converted into algorithms. – vzn Jun 07 '14 at 14:43
  • ??? re (2)/(3) are these lower or upper bounds? arent all algorithms in P sufficient? also the construction in the time hierarchy theorem mentioned in Thomas answer (basically enumerating/universally simulating TMs with "clocks") can even generate/enumerate all such languages... suggest juknas excellent ref boolean circuit complexity for survey in this overall area... – vzn Jun 07 '14 at 15:04
  • @Kaveh, as I mentioned above, we might have "small" circuits that look nothing like TMs for the same problem. (Or we might not...?) The fact that one could generate these circuits in polynomial time doesn't change that their structure would be fundamentally different from "trivial" converted-TM circuits. Time vs size isn't so important here; the point is they let us capture "triviality" vs "non-triviality". – usul Jun 07 '14 at 17:16
  • @vzn, (2)/(3) are asking for upper bounds, i.e. answers to (5) that are also asymptotically better than the best known trivial-conversion-of-a-TM. – usul Jun 07 '14 at 17:17

1 Answers1

8

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).

Thomas
  • 2,803
  • 19
  • 29
  • 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. – usul Jun 07 '14 at 01:41