IETF Logo Mail Archive

Re: [rrg] [ot] p=np !

heinerhummel@aol.com Tue, 06 September 2011 08:18 UTC

Return-Path: <heinerhummel@aol.com>
X-Original-To: rrg@ietfa.amsl.com
Delivered-To: rrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D10BA21F84D2 for <rrg@ietfa.amsl.com>; Tue, 6 Sep 2011 01:18:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.895
X-Spam-Level:
X-Spam-Status: No, score=-0.895 tagged_above=-999 required=5 tests=[AWL=1.103, BAYES_00=-2.599, HTML_MESSAGE=0.001, J_CHICKENPOX_12=0.6]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 37SBixCOLs8F for <rrg@ietfa.amsl.com>; Tue, 6 Sep 2011 01:18:13 -0700 (PDT)
Received: from imr-da05.mx.aol.com (imr-da05.mx.aol.com [205.188.105.147]) by ietfa.amsl.com (Postfix) with ESMTP id C375F21F84CD for <rrg@irtf.org>; Tue, 6 Sep 2011 01:18:09 -0700 (PDT)
Received: from mtaomg-ma04.r1000.mx.aol.com (mtaomg-ma04.r1000.mx.aol.com [172.29.41.11]) by imr-da05.mx.aol.com (8.14.1/8.14.1) with ESMTP id p868JaqL017164; Tue, 6 Sep 2011 04:19:36 -0400
Received: from core-dqc001c.r1000.mail.aol.com (core-dqc001.r1000.mail.aol.com [172.29.161.129]) by mtaomg-ma04.r1000.mx.aol.com (OMAG/Core Interface) with ESMTP id 16361E000081; Tue, 6 Sep 2011 04:19:36 -0400 (EDT)
References: <8CE39654461E569-F18-49E23@Webmail-d117.sysops.aol.com><1315203358.2952.1126.camel@home> <Pine.LNX.4.64.1109051601500.32042@lakka.kapsi.fi>
To: decoy@iki.fi, m.hallgren@free.fr
In-Reply-To: <Pine.LNX.4.64.1109051601500.32042@lakka.kapsi.fi>
X-MB-Message-Source: WebUI
Received: from 178.26.0.180 by angweb-usd004.sysops.aol.com (205.188.92.199) with HTTP (WebMailUI); Tue, 06 Sep 2011 04:19:35 -0400
MIME-Version: 1.0
From: heinerhummel@aol.com
X-MB-Message-Type: User
Content-Type: multipart/alternative; boundary="--------MB_8CE3A84D9260665_1EA0_1BED2_angweb-usd004.sysops.aol.com"
X-Mailer: AOL Webmail 34078-STANDARD
Message-Id: <8CE3A84D91A1F7B-1EA0-9C2D@angweb-usd004.sysops.aol.com>
X-Originating-IP: [178.26.0.180]
Date: Tue, 06 Sep 2011 04:19:36 -0400
x-aol-global-disposition: G
X-AOL-SCOLL-SCORE: 0:2:414688960:93952408
X-AOL-SCOLL-URL_COUNT: 0
x-aol-sid: 3039ac1d290b4e65d798595a
Cc: rrg@irtf.org
Subject: Re: [rrg] [ot] p=np !
X-BeenThere: rrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: IRTF Routing Research Group <rrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/rrg>, <mailto:rrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/rrg>
List-Post: <mailto:rrg@irtf.org>
List-Help: <mailto:rrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/rrg>, <mailto:rrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 06 Sep 2011 08:18:14 -0000

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 <decoy@iki.fi>
An: Michael Hallgren <m.hallgren@free.fr>
Cc: heinerhummel <heinerhummel@aol.com>; rrg <rrg@irtf.org>
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 - decoy@iki.fi, http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

v2.23.0 | Report a Bug | By Email