You can also mix problems to change the average complexity. Take SAT (in NPC) and encode each instance with a word over a binary alphabet (eg. A and B). Then a

You can also mix problems to change the average complexity. Take SAT (in NPC) and encode each instance with a word over a binary alphabet (eg. A and B). Then add 2SAT (in POLY) and encode it using an alphabet with four letters (eg. A, B, C and D). If a word has only As and Bs, treat it as SAT, otherwise as 2SAT. If you chose a random instance of length n (= a sequence of n letters from A to D), the probability it is from SAT (ie contains no C or D) is less than 1/2^n. Thus most instances are solvable in poly time, and only with neglectable probability you get a "harder" problem from SAT. Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.