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 AB ∈ 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
