0

Good afternoon everyone;

I am having difficulties to discriminate between NP and NP completeness. For instance, we know that a problem is in NP class should we try to find a algorithmic solution for this problem?

Regards,

Can
  • 171
  • I think you should first understand what the terms NP and NP-Complete mean. – Obinna Okechukwu Dec 27 '13 at 23:00
  • dear obinna; That's what I am trying to do actually. I looked at youtube videos and obviously Sipster's book. However, as I indicate in my question I am having difficulties. That's why I asked this question.Thank you. – Can Dec 27 '13 at 23:05
  • In simple terms - a problem is in class NP if given a solution to any instance of the problem, the solution can be verified in polynomial time. A problem is NP-Complete if it is NP-Hard and also in NP. A problem is NP-Hard if it is at least as hard as the hardest problem in NP (note that it doesn't necessarily have to be in NP). – Obinna Okechukwu Dec 27 '13 at 23:11
  • See: http://en.wikipedia.org/wiki/Computational_complexity_theory – Obinna Okechukwu Dec 27 '13 at 23:12
  • Should we try to solve a problem if we know that it is NP. My confusion comes from two arguments. P=NP or P<NP. Can NP problem could be solved such that it will work in polynomial time? – Can Dec 27 '13 at 23:15
  • see: http://math.stackexchange.com/questions/589634/how-to-prove-that-p-neq-np?rq=1 – Obinna Okechukwu Dec 27 '13 at 23:23

1 Answers1

2

Knowing that a problem is in $\mathrm{NP}$ does not mean that the problem is difficult; $\mathrm{P}$ is a subset of $\mathrm{NP}$, after all.

Being in $\mathrm{NP}$ only says that the problem's affirmative answer can be verified in polynomial time, with a bit of help (a witness). For example, the problem of "Is the number $X>1$ composite?" is in $\mathrm{NP}$; if someone wants to convince us that the answer is "yes", they can do so by producing a non-trivial factor of $X$ and we can, in polynomial time, verify that the factor indeed divides $X$ (and that it's non-trivial). If the answer is negative (i.e. when $X$ is prime), they can't fool us by providing fake witness.

We know that some problems in $\mathrm{NP}$, the so-called $\mathrm{NP}$-complete ones, are at least as hard as any other problem in $\mathrm{NP}$. If you manage to solve any $\mathrm{NP}$-complete problem in polynomial time, you'll be able to solve all of the $\mathrm{NP}$-complete problems in polynomial time and $\mathrm{NP}$ would be the same as $\mathrm{P}$. At the moment, we don't know whether it is possible to do so and even if it was, it'd likely be quite difficult. Thus, if you know that certain problem is $\mathrm{NP}$-complete, search for polynomial-time solution might be waste of time.

That being said, not being able to produce a polynomial-time algorithm for a problem does not mean that the problem cannot be solved fast enough (e.g. $O(n^{\log\log n})$ is not polynomial time, yet for $n\leq 10^8$, we have $n^{\log\log n}<n^3$), or that specific instances of the problem are not considerably easier than others. Furthermore, sometimes one doesn't really need the exact solution and an approximate one would be good enough; and the good news is that even some of the $\mathrm{NP}$-complete problems do admit fast approximation.

Peter Košinár
  • 10,810