Sampo,
The much greater impact stems from the germinal cell of the solution: converting all network links to arcs which are, loop-free, directed to some single or multiple destinations. At first this idea was rated VERY POOR by the EU-ICT project evaluator, then it was ignored (may be not even read) by rtgwg as well as by rrg (see TARA and the propagated method to build several topological maps of different zoom). Admitted, the STP has been the hardest though, but - with respect to your expections concerning the complexity - I have to warn you: 0,1 % of the performance for building the smallest Steiner Tree, 99,9 % of the performance for demonstrating that there can't be any smaller one. - my guess. And: it will take a crew of programmers to encode it. Heiner -----Ursprüngliche Mitteilung----- Von: Sampo Syreeni <[email protected]> An: Michael Hallgren <[email protected]> Cc: heinerhummel <[email protected]>; rrg <[email protected]> Verschickt: Mo, 5 Sept 2011 11:03 am Betreff: Re: [rrg] [ot] p=np ! On 2011-09-05, Michael Hallgren wrote: > Care to share proof? :) Though it's an interesting question what the practical impact on routing research would be. I'm pretty sure we'd have a reduction to something like O(n^100) even if true. Thus, zero impact, when even O(n^2) is already bad, and O(n^3) more or less inapplicable. -- Sampo Syreeni, aka decoy - [email protected], http://decoy.iki.fi/front +358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2
_______________________________________________ rrg mailing list [email protected] http://www.irtf.org/mailman/listinfo/rrg
