The recipe seems to be, pick a problem whose solution is highly verifiable, then throw the equivalent of ten billion hours of expert-level thought at it. If you can narrow the search space a lot, all the better. P != NP is sure to follow soon enough.
Their last two examples are extremely verifiable.