Dick Lipton, a CS theory prof at Georgia Tech, discusses his graduate complexity theory requirements. He is moving away from the problem solving aspects of the subjects, and insisting that his students better understand the definitions, axioms, key theorems, etc. of complexity theory. I don't think he is expecting them to memorize all of them – hopefully, he is trying to get them to understand how to use them to prove or derive other results. I think I would have benefited from this type of approach.
Former Googler Niniane Wang would like there to be games that teach computer science concepts such as regular expressions (regexes) and shortest-path algorithms. In one such game, you'd be given regexes and be asked to supply strings that the regexes accept. What is taught in complexity theory (and how it's taught) can differ quite a bit, but I'm not so sure this type of game could develop intuition for the types of problems I saw when I took the classes, such as:
- when given a description of a regular language, having to supply a finite automaton (FA) recognizing it or regular grammar generating it
- understanding the closure properties of FA
- understanding the equivalence of deterministic and nondeterministic FA
- understanding why a language is not regular