tag:blogger.com,1999:blog-3722233.post7643959447346237946..comments2019-02-20T01:09:24.082-05:00Comments on Computational Complexity: LOGCFL Venkat StyleLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-22960502153035831722018-11-29T14:47:04.298-05:002018-11-29T14:47:04.298-05:00A few years back I used to think that there is pot...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.<br /><br />Indeed, through non-trivial inductive counting one can show that bounded-AND-unbounded-OR circuits can be simulated by bounded-OR-unbounded-AND circuits.<br /><br />The only problem with the above statement is that it's not true (considering its implicit quantification).<br /><br />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:<br /><br />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. <br /><br />If one considers such circuits of size 2^poly(n) then this is (exactly) NP. <br /><br />Also, if we consider bd-AND-unbd-OR then we get coNP.<br /><br />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).<br /><br />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).<br /><br />-- PeriklisPeriklishttps://www.blogger.com/profile/01566397324053760799noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34425012956472715782018-11-28T19:35:31.772-05:002018-11-28T19:35:31.772-05:00The characterization by semi-unbounded circuits is...The characterization by semi-unbounded circuits is very nice indeed.<br />It shows that LOGCFL is the Boolean analogue of the arithmetic circuit class VP<br />(this follows from the depth reduction result for arithmetic circuits due to Valiant, Skyum, Berkowitz and Rackoff).Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.com