12
$\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?
Improve this question
$\endgroup$
3
  • 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, 2012 at 17:10
  • 4
    $\begingroup$ @Lucas, Factoring and GraphIso are conjectured to be NPI, also see this. $\endgroup$
    – Kaveh
    Apr 29, 2012 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, 2012 at 8:23

3 Answers 3

Reset to default
14
$\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.

Improve this answer
$\endgroup$
10
$\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.

Improve this answer
$\endgroup$
0
-2
$\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.

Improve this answer
$\endgroup$
4
  • $\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, 2013 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, 2013 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, 2013 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 'SO- stop being evil'
    Jun 3, 2013 at 19:10

Your Answer

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

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