Re: NP-complete and NP-Hard?

On Mon, 20 Jun 2005, yijun_lily@xxxxxxxxx wrote:

> Anybody can give me an example?Why is it significant to recognize a
> problem is NP,NP-Complete or NP-Hard?
>
> I can read the concepts about them, but I don't get their application
> and why they are usefull.

Take an algorithm A to solve problem P.

Suppose algorithm A works in time 2^n. Consider that n=100 (which is not a
very big value since we often manipulate much larger data, think about the
size of things such as, say, the database of customer of amazon.com, there
is much more than 100 people in it).

To solve problem P with n=100, algorithm A need 2^100 ~ 10^30 steps.
(2^100 = (2^10)^10 ~ (10^3)~10 ~ 10^30).

Consider you have a very powerfull computer, running at 10GHz (a bit
faster than current computer), that is making 10^10 operation per second.
To solve your problem, you'll still need 10^20 seconds, that make around
10^15 days (86400 seconds per day ~ 100 000=10^5).
So 3*10^12 years (10^3 days ~ 3 years).

More than 3 000 billions of years ! A bit too much.

Now, suppose that you have an algorithm B for saving the same problem P
that run in time n^2
If you need to solve the problem for, says, n=100 000.
This time, you'll need (10^5)^2=10^10 operation, meaning that this will be
solve in only 1 second on the same computer !

So, this is to illustrate a well-known mathematical fact: exponentiation
are much much larger than polynomial.

Back to P vs NP.

Suppose you want to solve problem P and have found algorithm A. You're
happy to have a solution, but your boss is unhappy because the solution is
no usable in practice, so he wants you to find something faster.

After a long time, you do not find anything really better. So now come the
questions: "does something better really exists ?"

If you manage to prove that problem P is NP-hard (or NP-complete, which is
a stronger condition), then you know that it is very unlikely that
apolynomial algorithm do actually exist and you will most probably not be
able to find algorithm B.

So you can go back to your boss and says "well, problem P is NP-hard, so
it's useless to try to find an algorithm better than A". And your boss
should then agree that looking for that is most likely a waste of time.



So that why it's important to be able to make distinction between P and
NP. If you proove a problem to be in P, then you also have a fast
algorithm to solve it.

If you do not have a fast algorithm, then you cannot know if it's because
there does not exist a fast algorithm or because you did not find it.

If you proove your problem to be NP-hard, then you know you don't have a
fast algorithm because there does not exists a fast algorithm.


[for the last paragraph, I implicitely supposed taht P != NP, which is not
prooved currently but only suspected, a better way to formulate that would
be to says that people are looking for such a fast algorithm since more
than 30 years and anybody who'll find one will get a huge prize, so you'll
probably not be able to find such a fast algorithm in 1 month of hard
work.]

[Being in P is not a real proof of being "fast to solve" since things such
as n^(10^100) are polynomial and any algorithm with such a running time
won't be fast. It's truly "faster than any exponential algorithm for
sufficiently larges values of n". Of course, practical values of n may be
small enough to make this assymptotical assumption false. Anyway, P is
often considered as "tractable problems" while problems not in P will be
considered as inctractable.]

Hypocoristiquement,
Jym.
.

Relevant Pages

  • Re: Building Unification Table - tranforming prolog like notation into lisp notation
    ... basic algorithm is a heavy user of resources. ... but fast algorithm in all but the worse cases. ... complexity like Obut also sometimes goes with huge constant ... Actually in complex programs it's more about implementation than ...
    (comp.lang.lisp)
  • converting adjacency matrix into a tree
    ... I'm looking for a fast algorithm to do the following: ... A DataTable has the following columns: ID, ParentID, Title, Body, etc. ... represents webforum conversation threads. ... I understand this can be done with recursion but my algorithm seems to be ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: JSH: Remarkably odd
    ... JSH wrote: ... programming happens to be NP-hard, which means that your algorithm won't ...
    (sci.math)
  • Re: NP - Hard -- Approximation algos
    ... > polynomial time. ... > algorithm which solves it. ... The real answer to question 2 is that the problem is NP-hard ... might be unhelpful - however, this question is more philosophical than ...
    (sci.crypt)
  • Re: More of an Algorithems question
    ... >How can I proove that no Algorithm can compress every file of length ... Prev by Date: ...
    (sci.math)
Loading