tag:blogger.com,1999:blog-3722233.post2632797971954315737..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Challenge: Is there a small NFA for { a^i : i\ne 1000} ?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-75756820974173251922018-04-05T13:25:21.193-05:002018-04-05T13:25:21.193-05:00Oh well, I see by the time I got back from vacatio...Oh well, I see by the time I got back from vacation, the solution has been posted and it's essentially the same...domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10066013234905897022018-04-05T13:17:06.633-05:002018-04-05T13:17:06.633-05:00I can see a sqrt(n) upper bound using the Frobeniu...I can see a sqrt(n) upper bound using the Frobenius coin problem, I wonder if it's the same that you have.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41527271848606727252018-04-03T14:35:32.894-05:002018-04-03T14:35:32.894-05:00I think the answer has already been known: http://...I think the answer has already been known: http://lics.siglog.org/lics00/short00/7.pdf<br /><br />Universal finite automaton recognizes the complement of this language (i.e. NFA recognizes this language) with \Theta(\sqrt(n)) states, where n=1000 for this language.Abunoreply@blogger.com