should we try to solve problem in np class

Question

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,

Answer 1

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.