H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end of December. In honor of Venkat I'd like talk about my favorite paper of his, relating LOGCFL to semi-unbounded circuits.Let's start with context-free languages. Even if you never took a theoretical computer science course, you probably saw them in elementary school.
A context-free language is a series of rules like S-> NP VP or N->man. The context-free part comes from the fact that a noun phrase (NP) produces the same sentence fragments wherever it appears. CFLs have a rich theory--there have been whole textbooks devoted to the topics.
LOGCFL are the set of problems that are reducible to context-free languages with a small-space reduction. Formally, A is in LOGCFL if there is a CFL B and a log-space computable function f such that for all x, x is in A if and only if f(x) is in B.
Venkat showed that LOGCFLs are equivalent to semi-unbounded circuits, log-depth circuits with unbounded OR gates but bounded AND gates, the class now called SAC1 (technically the equivalence holds for log-space uniform SAC1 but that's not important). His proof goes through various models of alternating Turing machines and push-down automata.
Context-free languages are not closed under complement, for example 0n1n0n is not context-free but its complement is. Somewhat surprisingly Borodin, Cook, Dymond, Ruzzo and Tompa showed that LOGCFL is closed under complement, combining the Immerman-Szelepcsényi inductive counting technique with Venkat's circuit characterization of LOGCFL.
The Borodin result implies that you whether you have bounded ORs and unbounded ANDs, or bounded ANDs and unbounded ORs, you compute the same class.
Enjoy your retirement Venkat. We'll miss you!
The characterization by semi-unbounded circuits is very nice indeed.
ReplyDeleteIt shows that LOGCFL is the Boolean analogue of the arithmetic circuit class VP
(this follows from the depth reduction result for arithmetic circuits due to Valiant, Skyum, Berkowitz and Rackoff).
A few years back I used to think that there is potentially something profound that we can say by thinking about semi-unbounded circuits. Now, I'm less hopeful.
ReplyDeleteIndeed, through non-trivial inductive counting one can show that bounded-AND-unbounded-OR circuits can be simulated by bounded-OR-unbounded-AND circuits.
The only problem with the above statement is that it's not true (considering its implicit quantification).
The statement is true for logarithmic depth circuits and, importantly, polynomial size. If instead of polynomial size we allow circuits up to size 2^poly(n) (depth is still O(logn)), then the following happens:
Consider uniform (e.g. AC0 uniform) circuits of size n^O(logn) and depth O(logn). Then, such circuits compute NSC^2. That is non-deterministic machines with (logn)^2 space and simultaneously polynomial time. More generally, 2^{(logn)^k} size does NSC^k.
If one considers such circuits of size 2^poly(n) then this is (exactly) NP.
Also, if we consider bd-AND-unbd-OR then we get coNP.
Btw, the reason why a polytime machine can use such superpoly circuits is because of the depth + the fact that the circuit is semi-unbounded yields "proofs" for given inputs that are of size 2^O(logn).
There are some reasons (e.g. proof complexity) to believe that NP =/= coNP. But still in a world where NP=coNP it'd have been very nice if a proof that NP=coNP had gone through inductive counting (inductive counting is a technique devised for space-bounded computation). The inductive counting in Borodin et al. won't work here for obvious reasons. We can think however about other forms of inductive counting for such circuits (or ATMs if you prefer).
-- Periklis
Professor
ReplyDelete1. Can we assume the SAC^i circuits to be alternating? Meaning unbounded fanin unbounded fanout OR gates are in alternating layer with bounded fanin unbounded fanout AND gates?
2. If so and if CC0=ACC0 (indicated by evidence provided in https://link.springer.com/article/10.1007/s00037-010-0287-z) would it be possible to replace the OR gates by CC0 circuit and since AND has fanin 2 every OR gate would be replaced by two copies of CC0 circuit and since there are polynomially many AND gates in every layer it appears every layer of AND gates can be replaced by polynomial sized CC0 layer and the overall SAC^i circuit can be simulated in CC^i. Is it correct?
3. So if CC0=ACC0 would it follow NC^1=CC^1=NL=SAC^1\subseteq NC^2\subseteq SAC^2=CC^2\subseteq SAC^3=CC^3 and so on?
Thank you.