[Solved]: Complexity classes that are closed under subtraction

Problem Detail: 

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!

Asked By : Andrea Williams

Answered By : Karolis Juodelė

$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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18897

 Ask a Question

 Download Related Notes/Documents