Re^2: Empirically solving complex problems

in reply to Re: Empirically solving complex problems
in thread Empirically solving complex problems

A problem described can be related to Knapsack or The Travalling Salesman Problem--correctly described as NP-hard or NP-complete--but it can still be solved in real time using Perl when the CS majors give up. I've done this many times.

The thing about NP complete problems is that they don't scale. It could be you can still find solutions for, for example, 20 nodes, while for just a few more nodes, solving the same problem takes many times longer, so long that it's no longer practically usable. Your particular problem may take a few minutes to solve, while the slighhtly more complex problem takes hours, or days.

Comment on Re^2: Empirically solving complex problems

Replies are listed 'Best First'.
Re^3: Empirically solving complex problems by tilly (Archbishop) on Mar 07, 2005 at 07:27 UTC
I think that BrowserUK's point is that a problem can be related to a known hard problem, but be very doable. Or there is a variation on it which is what you really need that is doable. The CS major looks at the problem and knows the theory about why it is hard. But if you just try it, often you'll get an answer. Sometimes you won't. Often you'll get a fast answer to the wrong problem. But success comes often enough that it is often worth not giving up too easily.	[reply]

Replies are listed 'Best First'.

Re^3: Empirically solving complex problems
by tilly (Archbishop) on Mar 07, 2005 at 07:27 UTC

BrowserUK

Sometimes you won't. Often you'll get a fast answer to the wrong problem. But success comes often enough that it is often worth not giving up too easily.

[reply]

In Section Meditations