I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know :

  • A-> B
  • A-> C
  • C -> B

A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for B. I know that A belongs to NP, B and C are NP-complete. Moreover I can write an algorithm for A with a quadratic number of calls to C. can I deduce something about the complexity of A?

  • 2
    $\begingroup$ What do you think? What have you tried? Would it make a difference if it were a cubic number of calls to C. $\endgroup$ – babou Apr 8 '15 at 10:40
  • $\begingroup$ I think that A is np-complete . $\endgroup$ – Gaëlle Hisler Apr 8 '15 at 10:48
  • 1
    $\begingroup$ And why? Can you sketch a proof (idea)? $\endgroup$ – Raphael Apr 8 '15 at 10:54
  • $\begingroup$ Voting to close as unclear, since the meaning of -> isn't defined and the asker hasn't visited the site in three years so is unlikely to clarify. As described, it sounds like it just means that A is a subset of B, which isn't enough to know anything useful. $\endgroup$ – David Richerby Dec 13 '18 at 14:20

You know that:

  1. A belongs to NP
  2. B is NP-Complete
  3. C is NP-Complete
  4. If A accepts given word then B accepts this word as well
  5. If we can solve C - we can solve A.

To prove that A is NP-Complete you need to prove that it belongs to NP (which is given to us) and that any problem from NP can be reduced to it (so that it is NP-Hard). To show the second one you need to show a reduction from an NP-Complete problem to A.

The last (5th) of our information basically means you have a polynomial reduction from A to C which is no surprise, since A is in NP and C is NP-Complete (meaning, among others, that every NP problem can be reduced to it, including A). This doesn't give you much about A (it only confirms that A is no harder than C).

The 4th information gives us knowledge like this: if some word belongs to A it also belongs to B, but there are some possible words that belong to B but not to A. In other words, A is a subset of B. This does not gives us much about A either, because A could belong to P only and still be a subset of B (as NP "contains" P).

In my opinion, if I understood this well, this information is not sufficient to say more about the complexity of A.

| cite | improve this answer | |
  • $\begingroup$ Assume that it exists a poly algo for A , this implies that C is poly too. If C is Poly this implies that SAT is poly, which is impossible. So for me I can conclude that it is not possible for A to be in P $\endgroup$ – Gaëlle Hisler Apr 8 '15 at 11:48
  • $\begingroup$ @GaëlleHisler Don't forget the "unless $P = NP$" part. $\endgroup$ – Luke Mathieson Apr 9 '15 at 3:54
  • $\begingroup$ Exactly. We do not know if $P ≠ NP$ (OK, we assume it is true, but it should not be used in proofs imho.) $\endgroup$ – 3yakuya Apr 9 '15 at 11:49

Let A = "Answer NO for everything", and all condition satisfy. Therefore we know nothing more about A

| cite | improve this answer | |

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.