tag:blogger.com,1999:blog-3722233.post3104560555660523151..comments2024-07-14T17:05:42.915-05:00Comments on Computational Complexity: Challenge about NFA for {a^y : y\ne 1000} answered.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-62810784013118402522018-04-07T06:56:21.833-05:002018-04-07T06:56:21.833-05:00Second Edition of my P vs NP efforts:
http://vix...Second Edition of my P vs NP efforts:<br /><br /> http://vixra.org/abs/1804.0076Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44800769085658722842018-04-06T10:11:36.393-05:002018-04-06T10:11:36.393-05:00nice/great idea but surprising nobody has thought ...nice/great idea but surprising nobody has thought of this before. did you do a literature search? did turn up this ref which seems somewhat related. as is called in software engr its a sort of "design pattern"...<br /><br />https://www.sciencedirect.com/science/article/pii/0304397595001298Anonymoushttps://www.blogger.com/profile/10048739391910999672noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35247787590807433252018-04-06T03:59:55.493-05:002018-04-06T03:59:55.493-05:00That's fascinating. Now, if one consider the s...That's fascinating. Now, if one consider the sequence mapping each n to the minimal number of states of an NFA that accepts {a^i | i ≠ n}, I wonder how many of these values we know exactly? Maybe it would make sense to add this to the OEIS...a3nmhttps://a3nm.net/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82394181836749233772018-04-05T15:02:20.884-05:002018-04-05T15:02:20.884-05:00There is a simpler proof. In this language, there ...There is a simpler proof. In this language, there are at least $1000$ distinct accepting suffix sets of the form $A_j = y_i$ for $i \neq j$.<br />Note that all the sets $A_j$ are incomparable with respect to $\subseteq$.<br /><br /> In any NFA with $n$ states, the set of accepting suffixes can contain at most $n$ pairwise-incomparable accepting suffix sets. Therefore, the NFA must contain at least 1000 states.<br />Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36145114359555266412018-04-05T11:37:32.242-05:002018-04-05T11:37:32.242-05:00Cicadas with a runway. Neat! If I understand corre...Cicadas with a runway. Neat! If I understand correctly, one thing this highlights is the difference in complementarity between DFAs and NFAs. Students that think, "oh, I'll equivalently look for NFAs that *only* accept 1000" would have a hard time, right?Andrew B.noreply@blogger.com