Re: Aspiring highest-order programmer

From: Ian Woods (newspub2_at_wuggyNOCAPS.org)
Date: 06/12/04 

Date: Sat, 12 Jun 2004 02:39:39 +0000 (UTC)

spinoza1111@yahoo.com (Edward G. Nilges) wrote in
news:f5dda427.0406111731.63eaf3cc@posting.google.com:

<snip>

> Thus it appears to me that "an algorithm whose complexity is
> nonpolynomial" has received undue focus in the literature when in fact
> the engineering problem is reducing the ORDER of a polynomial to the
> minimum possible level.

Many problems which are NP-complete (or harder) are significant
engineering problems and 'solving' them better has significant benefits
in a number of fields.

The point of 'NP' is to classify problems which are at some level
equivalent[1] and can't be solved in polynomial time[2]. They are
tremendously important to anyone devising or analysing new algorithms[3],
and anyone trying to solve a number of common problems[4].

There are certainly a number of quite fundamental problems in graph
theory which are in NP which large organisations would pay /billions/ to
be able to have a polynomial time solution for. Why? Simple: it'd save
them /trillions/ over the next decade... and I'm only thinking of the
TSP!

I'd argue that such a problem is definately worth study, since the
practical impact of a better solution is large!

Ian Woods

[1] They're equivalent in the sense that any problem in NP can be turned
into any other problem in NP by a polynomial time transform.

[2] As of this date, I don't know of anyone who has solved any NP
complete problem in polynomial time. If anyone had, it'd be the biggest
news in the field of software since, well... ever. It'd be almost as
newsworthy as someone solving the halting problem.

[3] If your 'new algorithm' happens to be convertable to a problem in NP
in polynomial time, the odds are that you've rediscovered a known
algorithm or found a new problem in NP.

[4] Knowing that you're trying to solve a problem in NP is exceedingly
useful in picking useful techniques to approximate good solutions. If
you're unaware that you're trying to solve a problem in NP you can waste
much time trying to find a 'good' solution to the problem. 

-- 
There is no sig.

Relevant Pages

  • 6P=NP: Proof: Nondeterministic Algorithm
    ... each time the algorithm is run the resulting guess may differ. ... be done in Oor polynomial time. ... verifies x if there exists a certificate y such ... Algorithm A verifies language L if for any string x Î ...
    (sci.math)
  • Re: Aspiring highest-order programmer
    ... > that today's programmers repeat the mistakes of the past because their ... not the algorithm choosen to solve it. ... it means that there is no known polynomial time algorithm to ... algorithm to solve any NP-complete problem, ...
    (comp.programming)
  • Re: JSH: Nearly done
    ... my response to your "polynomial time" below.) ... algorithms really are, so I'll tell you: For a factoring algorithm to ... it doesn't hurt to use recursion in a "proof of concept" ...
    (sci.math)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... where M is a Turing machine and p is a polynomial ... can be done in polynomial time. ... How do we verify that the algorithm we've found solves SAT? ... Consider, for a fixed integer k, the decision problem ALGSAT-k. ...
    (comp.theory)
  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)