begin quoting Darren New as of Fri, Jan 25, 2008 at 05:02:09PM -0800: > David Brown wrote: > >Without it, I've not proven what I intended to prove. Otherwise, we don't > >know if there isn't some yet-undiscovered algorithm out there that solves > >the problem more efficiently. If we can prove that all algorithms must use > >either O(2^2^n) space or time, the conclusion follows. > > Yes, but that's a really hard problem, which is the point I'm making. :-) > > Actually, proving this would probably lead to all kinds of good stuff > coming out of it for compiler theory and such.
There's been a lot of work done for tractable/intractable problems. > "The Traveling Salesman Problem: A problem that has been vexing computer > scientists for many decades, but which traveling salesmen solve on a > daily basis." Heh. Actually, IIRC, someone showed that if you can make assumptions about the problem (e.g., a planar graph), the TSP falls out of NP and into P. Plus, real Traveling Salesman don't need the optimal route. "Good Enough" is, well, Good Enough. In practice, a little creative inefficiency is extremly desirable... it's GOOD to be stuck in Anaheim for a couple of days, if you want to hit Disneyland. Relax the requirement to find an "optimal" solution, and it gets much easier. -- Good enough is good enuf And all that kind of stuff. Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
