tag:blogger.com,1999:blog-3722233.post7643959447346237946..comments2024-06-22T00:23:11.174-05:00Comments on Computational Complexity: LOGCFL Venkat StyleLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-63112738730905058542021-06-09T06:45:29.661-05:002021-06-09T06:45:29.661-05:00Professor
1. Can we assume the SAC^i circuits to...Professor <br /><br />1. 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?<br /><br />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?<br /><br />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?<br /><br />Thank you.Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22960502153035831722018-11-29T13:47:04.298-06:002018-11-29T13:47:04.298-06: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-28T18:35:31.772-06:002018-11-28T18:35:31.772-06: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