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!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Well, how would you decide if a word belongs to A\B? $\endgroup$
    – Karolis Juodelė
    Dec 11, 2013 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, 2013 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, 2013 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, 2013 at 22:51
  • 1
    $\begingroup$ @AndreaWilliams P is, whether NP is depends on whether NP = coNP, I think. $\endgroup$
    – G. Bach
    Dec 11, 2013 at 23:22

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$
2
  • $\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, 2013 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, 2013 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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