tag:blogger.com,1999:blog-3722233.post3938102020421687832..comments2024-11-14T17:42:16.782-06:00Comments on Computational Complexity: Half-Exponential No MoreLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-58850965177368867132024-06-26T11:54:51.401-05:002024-06-26T11:54:51.401-05:00Since BPP has poly-size circuits, a half exp lower...Since BPP has poly-size circuits, a half exp lower bound for EXP would imply BPP strictly in EXP. But for all we know, EXP, NEXP and even EXP^NP are in BPP and thus all have polynomial-size circuits. See <a href="https://doi.org/10.1016/S0019-9958(86)80012-2" rel="nofollow">Heller</a>.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32238962461558038272024-06-26T11:46:31.499-05:002024-06-26T11:46:31.499-05:00An added question.. you said only third level had ...An added question.. you said only third level had exp circuits proof and this gave only half exp circuits for second level. Now since we have exp size circuits proof for second level, do we have half exp circuits size proof for first level which is Exp? So may be we are half way to P=BPP ;) ??Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84227059862044829252024-06-26T07:41:54.581-05:002024-06-26T07:41:54.581-05:00That's right but still pretty far. We don'...That's right but still pretty far. We don't know how to get over the relativization barrier.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23412696355360170042024-06-25T21:04:40.349-05:002024-06-25T21:04:40.349-05:00So E requires Exp size circuits implies P=BPP righ...So E requires Exp size circuits implies P=BPP right? How far away are we?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88906146889101811172024-02-20T02:30:43.589-06:002024-02-20T02:30:43.589-06:00niceniceAnonymousnoreply@blogger.com