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. Then add 2SAT (in POL

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. Then add 2SAT (in POLY) and encode it using an alphabet with four letters. If you chose a random instance of length n, the probability it is from SAT is less than 1/2^n. Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.