10
$\begingroup$

My book states this

  • If a decision problem B is in P and A reduces to B, then decision problem A is in P.
  • A decision problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
  • A decision problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

So my questions are

  1. If B or C is in NP-complete, and all problems in NP reduce to an NP-complete problem, using the first rule, how can any NP problem not be NP complete?
  2. If A reduces to B, does B reduce to A?
$\endgroup$

migrated from stackoverflow.com Apr 27 '12 at 12:14

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ Interesting fact related to your #1: If P is not equal to NP, we know that there must be NP problems that aren't NP-complete (this is called Ladner's theorem. see NP Intermediate). The weird thing is that we aren't sure of any common computation problems that fit in this category. The problem used in Ladner's theorem is artificially constructed to prove the theorem, but is practically unimportant. $\endgroup$ – Lucas Cook Apr 27 '12 at 17:10
  • 4
    $\begingroup$ @Lucas, Factoring and GraphIso are conjectured to be NPI, also see this. $\endgroup$ – Kaveh Apr 29 '12 at 6:59
  • $\begingroup$ @Kaveh: Nice list of NPI candidates, thanks! To clarify, I was saying that we aren't "sure" of a natural NPI problem with the same certainty as Ladner's problems. That is, if $P \neq NP$, the only NPI problems known for certain are artificial ones related to Ladner's hierarchy. $\endgroup$ – Lucas Cook Apr 29 '12 at 8:23
13
$\begingroup$

If A reduces to B, does B reduce to A?

No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a while(true) tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be reduced to any such algorithm A.

The basic idea is that if there is a reduction from A to B you can learn that B is at least as hard to solve then A and requires an algorithm that is at least as powerful.

So if a problem A reduces to an easy problem B, then we can deduce A is easy (since the reduction gives us the efficient algorithm) and if a hard problem A reduced to a problem B, we can deduce that B is also hard (since if B were easy then A would have to be easy too). However there is still the possibility of making a silly reduction from an easy problem to a hard problem but in this case we can't deduce any conclusions.

$\endgroup$
8
$\begingroup$

If B or C is in NP Complete, and all problem in NP reduce to an NP Complete problem, using the first rule, how can any NP problem not be NP complete?

The first rule is about problems in P. It has nothing to do with NP completeness. If problem A is NP Complete and problem B reduces to A, that does not mean that B is NP Complete.

If A reduces to B does B reduce to A?

Not generally, no.

$\endgroup$
  • $\begingroup$ "Not generally, no.", why? A little bit of explanation might also be useful for newbies. Also an explanation for your first answer should be provided. $\endgroup$ – nbro Aug 24 '15 at 14:22
-1
$\begingroup$

I have only the basic idea regarding NPC and NP Problems. But All i want to comment is about "If A is reduced to B then B is reduced to A? "

Simply consider a set A having {2,3,4,5} elements and set B having {3,4} in it. So A can be reduced to B. But B can't be reduced to A. Instead B can be expanded to A if B gains {2,5} elements.

But if A and B are having the same. then A can be reduced to B or B can be reduced to A.

$\endgroup$
  • $\begingroup$ This is not at all the right idea of reduction. Reduction isn't about sets gaining or losing elements. Rather, it's about being able to convert an instance of one problem into another using a Turing machine/algorithm. $\endgroup$ – jmite Jun 3 '13 at 16:36
  • $\begingroup$ Ok. So, If any problem is being reduced to another using any algorithm then it is not possible to regain the problem from the reduced output using that same algorithm again. $\endgroup$ – Naveen CS Jun 3 '13 at 16:51
  • 1
    $\begingroup$ I'm not totally sure what you mean, but I think it is not possible. If I'm not mistaken, these reductions can be many to one. A reduces to B if a polynomial number of calls to a subroutine solving B allows A to be solved in polynomial time. Different instances of A could invoke a call the same instance of B. $\endgroup$ – jmite Jun 3 '13 at 16:55
  • 2
    $\begingroup$ The question is about decision problems, not about sets. How is it useful to look at sets? Using the word “reduced” to mean that a set is a superset of another isn't even common terminology. $\endgroup$ – Gilles Jun 3 '13 at 19:10

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.