tag:blogger.com,1999:blog-6555947.post8899708679586938751..comments2024-04-08T04:56:51.603-06:00Comments on The Geomblog: Things that make you pull your hair out in despairSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-6555947.post-40130188534025169202007-08-21T19:05:00.000-06:002007-08-21T19:05:00.000-06:00What is the status of non-uniform AC0[6]?What is the status of non-uniform AC0[6]?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-72780125750609100342007-08-07T17:32:00.000-06:002007-08-07T17:32:00.000-06:00It's possible that NEXP is contained in non-unifor...It's possible that NEXP is contained in non-uniform AC0[6].Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-57036951407923676852007-08-07T17:06:00.000-06:002007-08-07T17:06:00.000-06:00Suresh probably meant uniform AC^0[6] for which th...Suresh probably meant <I>uniform</I> AC^0[6] for which the halting problem example doesn't work. Allender and Gore proved that the Permanent is not in uniform AC^0[6] but that doesn't rule out NP being contained in uniform AC^0[6].Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-39643505192624648222007-08-07T15:12:00.000-06:002007-08-07T15:12:00.000-06:00If HALTING is in AC0, can't we just solve any reco...If HALTING is in AC0, can't we just solve any recognizable problem in AC0 as well? But this obviously can't be true as we know that very simple things like PARITY are not in AC0!Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-26192475580383376982007-08-07T14:57:00.000-06:002007-08-07T14:57:00.000-06:00"Halting problem (unary input) is in AC0"Why?!<I>"Halting problem (unary input) is in AC0"</I><BR/><BR/>Why?!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1175445804251342752007-08-07T11:00:00.000-06:002007-08-07T11:00:00.000-06:00Halting problem (unary input) is in AC0 so AC0[6]i...Halting problem (unary input) is in AC0 so AC0[6]<BR/>is not equal to NP.<BR/>I believe the open problem<BR/>is whether NP belongs to AC0[6] or not.<BR/><BR/>Or do I ignore sth here?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-90682213987212222562007-08-06T10:17:00.000-06:002007-08-06T10:17:00.000-06:00Yes, I mean 'is a strict subset of'. I fixed it. t...Yes, I mean 'is a strict subset of'. I fixed it. thanks.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-14612769828836752152007-08-06T06:18:00.000-06:002007-08-06T06:18:00.000-06:00No I guess he means "is a strict subset of"!No I guess he means "is a strict subset of"!Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-25919782465094995032007-08-06T03:26:00.000-06:002007-08-06T03:26:00.000-06:00When you say "contained within", I assume you mean...When you say "contained within", I assume you mean "separated from".Anonymousnoreply@blogger.com