tag:blogger.com,1999:blog-3722233.post2275048041517285399..comments2024-03-28T14:56:46.834-05:00Comments on Computational Complexity: Identities in Computational ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-23562617996648702852023-03-28T12:43:34.087-05:002023-03-28T12:43:34.087-05:00RE (recursively enumerable) and CE (computably enu...RE (recursively enumerable) and CE (computably enumerable) are the same class. I find the latter more appealing.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10635953305215746382023-03-28T12:36:42.346-05:002023-03-28T12:36:42.346-05:00Do you mean MIP*=RE?
- Michael C.Do you mean MIP*=RE?<br /><br />- Michael C.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33390712276252792232023-03-19T22:06:18.882-05:002023-03-19T22:06:18.882-05:00Correction: It should be "FO(+,x) = Logarithm...Correction: It should be "FO(+,x) = <a href="https://complexityzoo.net/Complexity_Zoo:L#lh" rel="nofollow">Logarithmic Time Hierarchy</a> = DLOGTIME-uniform AC0".Aidan Evansnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12783134490868749562023-03-19T18:20:02.226-05:002023-03-19T18:20:02.226-05:00To explain upon the "AC0 = FO":
If we e...To explain upon the "AC0 = FO":<br /><br />If we extend FO with arithmetic predicates (i.e., addition and multiplication), denoted FO(+,x), then we get that FO(+,x) = DLOGTIME = DLOGTIME-uniform AC0.<br /><br />If we have FO with the ability to use an arbitrary numerical predicate, denoted FO(Arb), then we get that FO(Arb) = non-uniform AC0.<br /><br />Then, in line with the above anonymous comment, if we extend FO with an ordering relation, denoted FO(<) (i.e., FO over ordered structures), then we get that FO(<) = star-free regular languages.<br /><br />Subtle distinctions but important because FO(<) \subset FO(+,x) \subset FO(Arb). Aidan Evanshttps://aidantevans.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77513846478798367822023-03-17T05:22:35.076-05:002023-03-17T05:22:35.076-05:00Many interesting ones in regular languages too: MS...Many interesting ones in regular languages too: MSO=REG, FO=Star-Free, ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89680584192178944322023-03-17T00:55:28.686-05:002023-03-17T00:55:28.686-05:00Nice Thursday complexity post.Nice Thursday complexity post.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86168197866460386502023-03-16T16:57:51.552-05:002023-03-16T16:57:51.552-05:00Not exactly a complexity identity, but also "...Not exactly a complexity identity, but also "Turing equivalence" leads to some suprising "identities", too.Anonymousnoreply@blogger.com