0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Well, how would you decide if a word belongs to A\B? $\endgroup$ – Karolis Juodelė Dec 11 '13 at 21:05
  • $\begingroup$ Hint: if a language class is closed under subtraction, it contains $A \setminus A$. $\endgroup$ – Gilles 'SO- stop being evil' Dec 11 '13 at 21:28
  • 1
    $\begingroup$ 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. $\endgroup$ – G. Bach Dec 11 '13 at 22:12
  • $\begingroup$ @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. $\endgroup$ – Andrea Williams Dec 11 '13 at 22:51
  • 1
    $\begingroup$ @AndreaWilliams P is, whether NP is depends on whether NP = coNP, I think. $\endgroup$ – G. Bach Dec 11 '13 at 23:22
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, thanks! As @G. Bach suggested, i have concluded that P is closed under subtraction whereas NP isn't. $\endgroup$ – Andrea Williams Dec 11 '13 at 23:56
  • 1
    $\begingroup$ @AndreaWilliams Just to be clear, I don't know whether NP is closed under subtraction. $\endgroup$ – G. Bach Dec 12 '13 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.