Doug and Yuriy, (01)
I don't want to get into all the issues with all their ramifications.
But I'd just like to comment on the following two points. I'm sending
this note to Ontolog Forum because it's of general interest. (02)
DF
>> Note that an NP-hard problem, may, for restricted input be easy
>> to solve rapidly. Such solutions can be used and often are. (03)
YM
> It's true. Some "incorrect" heuristics may work better than formally
> correct algorithms but what's behind of the "context" and "heuristics"? (04)
Doug was not talking about "incorrect" heuristics, but about very
accurate approximations with precise error bounds. (05)
A typical example is the traveling salesman problem. If you have N
cities and you try to find the shortest possible circuit that visits
every city exactly once, you have to check every possible combination. (06)
For that problem, every exact algorithm takes time that is exponential
in N. But if you are satisfied with some approximation, say within 1%
of the shortest distance, you can find a good circuit in polynomial
time. And that time decreases further if you increase the bounds
to 2%, 5%, 10%... (07)
More generally, studies show that efficient approximations to NP
complete problems can often be found by *increasing* the search
space by going from discrete Boolean and integer representations
to the uncountable infinity of the real numbers. (08)
Following is a book-length analysis of those issues: (09)
Blum, Lenore, Felipe Cucker, Michael Shub, Steve Smale (1998)
Complexity and Real Computation, Springer-Verlag, Berlin. (010)
And following is a 25-page survey and discussion: (011)
http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf
Computing over the reals: where Turing meets Newton (012)
John (013)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (014)
|