Re: Why NP Problem is Important and Practical Examples

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 01/12/05 

Date: Wed, 12 Jan 2005 11:57:30 -0500

jrefactors@hotmail.com wrote:
> NP problem = problems that cannot be solved in polynominal running
> time.

Nicholas has already said that this is incorrect. In fact, it's a
fairly common misconception. Problems in NP are those for which
there exists a *nondeterministic* algorithm that produces the
answer in polynomial time (measured as a function in the length
of the problem instance). Stated simply, the "N" in NP comes
from "_N_ondeterministic _P_oly-time solution" rather than "_N_o
_P_oly-time deterministic solution."

An equivalent formulation of NP is that a problem is in NP if
there is a poly-time algorithm to verify a particular solution.
Take, for example, the problem SAT: given a boolean expression,
is there an assignment of truth values to the variables that
makes the formula true? For example, an instance of SAT might
be the expression

   (x_1 AND NOT x_2) OR (NOT x_1 OR x_3 AND (x_2 OR x_4))

You might well imagine that for a large expression of this type
it would be difficult to find values for x_i that would make this
true. However, it is easy enough to verify that x_1 = TRUE,
x_2 = FALSE, and an arbitrary assignment to x_3 and x_4 would
make the expression true. Thus, it's easy to generalize that
SAT is a problem in NP. On the other hand, SAT doesn't seem
to be solvable by an efficient deterministic algorithm: Sure,
you could always just try combinations of assignments to all
the variables, but with n variables, you might have to look
at all 2^n possible truth assignments and 2^n possible cases
to verify would take longer than any polynomial number of steps.

Loosely speaking, this is why grading homework seems easier than
doing the homework--the former task is verifying a given answer
while the latter is producing the answer. The important question
is, does this sort of behavior always hold, namely are there
problems that are truly harder to solve than they are to verify?
Stated in another way the question is "does nondeterminism allow
the efficient (i.e., poly-time) solution of problems that can't
be solved efficiently in a deterministic fashion?" NOBODY KNOWS.

> I studied that in algorithms class, but I never understand why we
> care about that?

Here's a practical example, from an email I received recently from
a former student. There is a large collection of problems in NP
called "NP-complete." Without going into detail, in a sense these
are the "hardest" of the NP problems: if you could find a deterministic
poly-time solution to one of these, then *all* NP problems could
be solved in deterministic poly-time. This would be an immensely
important result and a lot of very smart people have worked on
this problem (known as the "P = NP?" question) for many years
without coming up with an answer (that's a more precise formulation
of the "NOBODY KNOWS" I used in the last paragraph).

My student was working as a software developer and he was meeting
with his group, discussing the application they were developing.
One possible implementation involved writing a particular algorithm;
my student recognized that the algorithm would have solved
one of those NP-complete problems, concluded that it was
unlikely that anyone would be able to find an algorithm that
would run in a feasible amount of time, and suggested that they
needed to find another approach.

My student wrote to me that (1) he never imagined that he would
ever have reason to refer to NP problems in his job and, even
more important, (2) he achieved instant respect from his peers
and his boss for pointing them away from a time-wasting avenue
of investigation.

Hope this helps. I apologize for the length.

Rick

p.s. For those in the know, I should note that I'm aware that
this sounds a lot like the introduction in Gary and Johnson,
but I have no reason to believe that the student's account
was anything less than completely truthful.

Relevant Pages

  • Re: PRINTING DIAMOND SHAPE WITH LOOPS!
    ... Okay, Paul, et al., ... > falsely not to be a student, while explaining what kind of student you are. ... > of place in a simple, deterministic algorithm like this. ...
    (comp.lang.java.programmer)
  • Re: PRINTING DIAMOND SHAPE WITH LOOPS!
    ... > stereotypes. ... Neither unfair nor a stereotype. ... falsely not to be a student, while explaining what kind of student you are. ... deterministic algorithm like this. ...
    (comp.lang.java.programmer)
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Re: decidable
    ... exist a proof of A and we have an effective procedure (or algorithm) to ... we have an algorithm to verify this". ... decidability we need not just an algorithm to verify that a sentence ...
    (sci.logic)
  • Re: Is code duplication allowed in this instance?
    ... code duplication, I suppose such terms like 'DRY' are meant to back ... So in this scenario is it OK to duplicate the algorithm to be tested ... within test codes to verify itself. ... as rigorous as preparing the data set with the known ...
    (comp.lang.python)
Loading