# Complexity classes that are closed under subtraction

Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't. Question was edited

Original question: Im having some hard time figuring out what languages are closed under subtraction. Say you have 2 languages A, B ∈ NP. Is A\B ∈ NP? what about P?

Commenters: My original question was extremely not accurate so i rephrased :)

Thanks!

• Well, how would you decide if a word belongs to A\B? – Karolis Juodelė Dec 11 '13 at 21:05
• Hint: if a language class is closed under subtraction, it contains $A \setminus A$. – Gilles 'SO- stop being evil' Dec 11 '13 at 21:28
• Languages isn't what you're actually interested in, you want to know whether a given complexity class is closed under subtraction of languages in that class. – G. Bach Dec 11 '13 at 22:12
• @G. Bach thats what i was trying to ask, are NP or P closed under subtraction? I was trying to think of an example and that is why i (mistakenly) refered to A and B. – Andrea Williams Dec 11 '13 at 22:51
• @AndreaWilliams P is, whether NP is depends on whether NP = coNP, I think. – G. Bach Dec 11 '13 at 23:22

$A \setminus B$ is defined as $\{x | x \in A ~ and ~ not ~ x \in B \}$. If you know the complexity of checking $x \in A$ and $x \in B$, what does that tell you about the complexitty of $x \in A \setminus B$? Can you see the algorithm for checking it?