Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
thank you for the pointer, and congrats to the nice results you obtained! Back then, we suspected that there would be such a parameter that governs NFA size, but were not having the right tools at hand.
A plus point is that the wikipedia list is both curated and regularly updated, in contrast to the list by Crescenzi and Kann - which has been discontinued in the 2000s. It's good to have those resources at hand when you're trying to establish NP-hardness of some graph problem. In my own research, I have successfully made use of the original Garey & Johnson 1979 list, which seems to be among the first of that kind.
@Jon Bannon: listening to an accordion is very different from digesting mathematical papers. Maybe modern art and modern poems would be a better analogy, because not every layperson will intuitively enjoy them on first sight. I share your viewpoint BTW.
