Date: 29 Jun 2011 12:06
Number of posts: 6
RSS: New posts
Sure. Every NPC language is decidable and decidable languages are closed under intersection.
Let me correct that - A verifier for L1 n L2 will check the certificate for L1 in polynomial time. If it accepts, It will check the same certificate for L2 in polynomial time. pol + pol = pol.
Hmmm…Coming to think of it, The intersection of SAT and Clique is empty, Yet the empty language is not NPC. So I guess this is the counter example.