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.
Comments
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.