Editing Stephen Cook (section)

===Some other contributions===
He named the complexity class [[NC (complexity)|NC]] after [[Nick Pippenger]]. The complexity class [[SC (complexity)|SC]] is named after him.<ref>{{cite web|title="Steve's class": origin of SC|url=https://cstheory.stackexchange.com/q/9298 |work=Theoretical Computer Science – Stack Exchange}}</ref> The definition of the complexity class [[AC0|AC<sup>0</sup>]] and its hierarchy [[AC (complexity)|AC]] are also introduced by him.<ref>{{cite web|title=Who introduced the complexity class AC?|url=https://cstheory.stackexchange.com/q/12649|work=Theoretical Computer Science – Stack Exchange}}</ref>

According to [[Don Knuth]] the [[KMP algorithm]] was inspired by Cook's automata for recognizing concatenated palindromes in [[linear time]].<ref>{{cite web|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858}}</ref>