I think I understand that a P class problem is reducible to an NP class problem (P≤NP).

I´d like to understand if I need to figure out a potential algorithm which could solve the NP class problem to know if it can be used as a subroutine for a P class problem.

So for example, if I ask you if the problem from class P —sum of integers— is reducible to a problem of class NP —Clique graph problem—, how would you reply to it?

Is this a valid reduction as the more complicated Clique problem is NP and the easier problem sum of integers is a P problem even though they deal with different math branches (one being algebra and the other one being graph theory)?

  • 1
    $\begingroup$ You might want to double-check which direction of reduction you are asking about. Also, saying "problem P (sum of integers)" - P is not a problem, it is a class of problems (and labelling a problem P is super-confusing since P usually means the class of problems solvable in polynomial time). Anyway, one way to figure out if such a reduction exists is to try to find one, and see if you can come up with one. $\endgroup$
    – D.W.
    Dec 18 '17 at 3:51
  • $\begingroup$ @D.W.: Thanks, I have updated my question. If you like send me an answer and I´ll accept it. I guess I would not be able to find a reduction as the two problems are unrelated. $\endgroup$ Dec 18 '17 at 11:43
  • $\begingroup$ Be careful with terminology. "a P class problem is reducible to an NP class problem" -- do you mean that there are such problems, or that the statement holds true for all pairs? "P≤NP" -- what does that mean? $\endgroup$
    – Raphael
    Dec 18 '17 at 11:58
  • $\begingroup$ You should be careful with calling problems 'unrelated'. In mathematics (and by extension, in computer science) problems that appear completely different at first glance quite often turn out to be related in some form. $\endgroup$
    – Discrete lizard
    Dec 18 '17 at 12:00
  • $\begingroup$ Thanks, I am not really an expert at math, that´s why I asked in the first place. $\endgroup$ Dec 18 '17 at 12:01

If you have a problem $X$ that is in P, then you can construct a polynomial time reduction to any problem $Y$ in NP (or in 'any' other class of problems*). This is possible, as our 'reduction' is allowed to spend polynomial time on the input of $X$, so it can simply determine whether a given input $I$ for $X$ is a 'yes'-input in polynomial time and map to a trivial input for $Y$ with the same truth-value.

*: To be precise, any decision problem such that we can find at least one 'yes'-instance and one 'no'-instance, which holds for pretty much any interesting decision problem.

  • $\begingroup$ Thank you for your answer, this is for some homework I have to do. I´ll tell the professor that I had to ask here and you kindly offered some help. $\endgroup$ Dec 18 '17 at 12:19

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.