Subject: [rrg] p=np !

From: [email-masked]
Date: Sun, 4 Sep 2011 18:01:00 -0400 (EDT)

I like to assure all on this mailing list that P = NP.

I hope this will have some impact on IETF technology, won't it ? Of course, one can always ignore whatsoever. But forever ???

In the past it occurred many times that I thought "this is it" wrt this issue, but in the next moment I only knew how  the network situation must be as to make my  algorithm  fail. 

But now things are different... :-)

Heiner

---

From: JinHyeock Choi <[email-masked]>
Date: Mon, 5 Sep 2011 07:17:33 +0900

> I like to assure all on this mailing list that P = NP.

You mean
it has been proved that P = NP?

if so, would you provide a pointer to a relevant article?

That could bring forth a huge impact.

best regards

JinHyeock

---

From: Tony Li <[email-masked]>
Date: Sun, 4 Sep 2011 17:10:02 -0700

> if so, would you provide a pointer to a relevant article?

I'm not seeing anything in the press.  I can only infer that Heiner is asking us to take this on faith.

Tony

---

From: Michael Hallgren <[email-masked]>
Date: Mon, 05 Sep 2011 08:15:58 +0200

Le dimanche 04 septembre 2011 à 18:01 -0400, [email-masked] a
> I like to assure all on this mailing list that P = NP. 

Heiner,

Care to share proof? :)

mh

> 
> I hope this will have some impact on IETF technology, won't it ? Of
> course, one can always ignore whatsoever. But forever ??? 
> 
> 
> 
> In the past it occurred many times that I thought "this is it" wrt
> this issue, but in the next moment I only knew how  the network
> situation must be as to make my  algorithm  fail. 
> 
> 
> _______________________________________________
> rrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/rrg

---

From: Sampo Syreeni <[email-masked]>
Date: Mon, 5 Sep 2011 16:03:41 +0300 (EEST)

> 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-masked], http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

---

From: [email-masked]
Date: Mon, 5 Sep 2011 16:39:23 -0400 (EDT)

Sorry, I can't. 
It is only myself who thinks to have developed a solution for a np-hard problem. Precisely for the Steiner Tree problem.
A solution by which any possible lever is applied to improve a current Steiner Tree until no further lever can quench out any more weight reduction of the tree at all.

I am not a man the press is interested in. Hence I cannot refer to any press news.

Heiner

-----Ursprüngliche Mitteilung----- 
Von: JinHyeock Choi <[email-masked]>
An: heinerhummel <[email-masked]>
Cc: rrg <[email-masked]>
Verschickt: So, 4 Sept 2011 8:17 pm
Betreff: Re: [rrg] p=np !

You mean

best regards

JinHyeock

---

From: [email-masked]
Date: Tue, 6 Sep 2011 04:19:36 -0400 (EDT)

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