tag:blogger.com,1999:blog-3722233.post4139075556580650905..comments2023-09-28T12:45:24.391-05:00Comments on Computational Complexity: Shuffling AroundLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-3330438262009846742020-12-11T09:57:51.118-06:002020-12-11T09:57:51.118-06:00Another recipe to prove P != NPAnother recipe to prove P != NPalturkistanyhttps://www.blogger.com/profile/16830837547945615050noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27621667014095732552020-12-10T01:38:37.778-06:002020-12-10T01:38:37.778-06:00Oops.
I wonder how I make these mistakes. (01)* w...Oops.<br /><br />I wonder how I make these mistakes. (01)* was my first thought but then somehow I began equating (01)* with [01]* (in programming notation; aka (0+1)* in math notation), and I spent quite some time not realizing these are different. In hindsight, it doesn't make any sense.<br /><br />Oh, well. I don't understand myself.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17659120585081426162020-12-09T15:30:39.476-06:002020-12-09T15:30:39.476-06:00"Why can't we have an open-book exam?&quo..."Why can't we have an open-book exam?"<br /><br />"Because then I'd have to write a question so complex no book would have the answer."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80823037737289202072020-12-09T15:19:57.676-06:002020-12-09T15:19:57.676-06:00He's right. perm((10)*) is the language of str...He's right. perm((10)*) is the language of strings with an equal number of 0s and 1s. The strings 0^n are distinguished by the strings 1^n. Myhill-Nerode: game over.Brendan Jubahttps://www.blogger.com/profile/03853337075953858702noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82117167056525439862020-12-09T14:24:51.714-06:002020-12-09T14:24:51.714-06:00I don't follow: The permutation of (10)* is (1...I don't follow: The permutation of (10)* is (10)*, hence regular.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82791812823080749762020-12-09T12:53:16.766-06:002020-12-09T12:53:16.766-06:00L=(10)* is regular, the permutation requires count...L=(10)* is regular, the permutation requires counting. Right?Andrew B.https://www.blogger.com/profile/02903366372812261992noreply@blogger.com