Apidesign at 18:44, 25 December 2011 - 2011-12-25 18:44:02

←Older revision Revision as of 18:44, 25 December 2011
Line 7: Line 7:
Nice observation ;-) Probably I am disappointed by the enthusiasm followed by total failure of P == NP proof published by Vinay Deolalikar and thus I am assuming P != NP.
Nice observation ;-) Probably I am disappointed by the enthusiasm followed by total failure of P == NP proof published by Vinay Deolalikar and thus I am assuming P != NP.
-
Btw. now, when there is an expert reviewing my proof, I share my only worry: What if, in the process of replacing dependencies by transitive dependencies, the amount of dependencies is increased to <math>2^n</math>? That would just replace an [[NP-Complete]] problem with polynomial problem of exponential size...
+
Btw. now, when there is an expert reviewing my proof, I share my only worry: What if, in the process of replacing dependencies by transitive dependencies, the amount of dependencies is increased to <math>2^n</math>? That would just replace an [[NP-Complete]] problem with polynomial problem of exponential size... On the other hand, that is not likely, I guess as the transitive dependencies will contain only one version from multiple incompatible versions.
--[[User:Apidesign|Apidesign]] 18:39, 25 December 2011 (UTC)
--[[User:Apidesign|Apidesign]] 18:39, 25 December 2011 (UTC)

Apidesign at 18:43, 25 December 2011 - 2011-12-25 18:43:01

←Older revision Revision as of 18:43, 25 December 2011
Line 6: Line 6:
Nice observation ;-) Probably I am disappointed by the enthusiasm followed by total failure of P == NP proof published by Vinay Deolalikar and thus I am assuming P != NP.
Nice observation ;-) Probably I am disappointed by the enthusiasm followed by total failure of P == NP proof published by Vinay Deolalikar and thus I am assuming P != NP.
 +
 +
Btw. now, when there is an expert reviewing my proof, I share my only worry: What if, in the process of replacing dependencies by transitive dependencies, the amount of dependencies is increased to <math>2^n</math>? That would just replace an [[NP-Complete]] problem with polynomial problem of exponential size...
--[[User:Apidesign|Apidesign]] 18:39, 25 December 2011 (UTC)
--[[User:Apidesign|Apidesign]] 18:39, 25 December 2011 (UTC)

Apidesign at 18:39, 25 December 2011 - 2011-12-25 18:39:22

←Older revision Revision as of 18:39, 25 December 2011
Line 1: Line 1:
-
A polynomial algorithm implies that the problem is not NP-Complete only if you assume that P != NP for which see http://en.wikipedia.org/wiki/P_versus_NP_problem.
+
A polynomial algorithm implies that the problem is not NP-Complete only if you assume that P != NP for which see [[wikipedia:P_versus_NP_problem|P versus NP]].
-
However, the important point that a known polynomial algorithm is more clearly bounded that a NP-Complete algorithm is fair enough.
+
However, the important point that a known polynomial algorithm is more clearly bounded that a [[NP-Complete]] algorithm is fair enough.
 +
 
 +
-- A comment from unknown reader
 +
 
 +
Nice observation ;-) Probably I am disappointed by the enthusiasm followed by total failure of P == NP proof published by Vinay Deolalikar and thus I am assuming P != NP.
 +
 
 +
--[[User:Apidesign|Apidesign]] 18:39, 25 December 2011 (UTC)

Glyn: Perhaps P=NP - 2011-12-23 08:35:39

Perhaps P=NP

New page

A polynomial algorithm implies that the problem is not NP-Complete only if you assume that P != NP for which see http://en.wikipedia.org/wiki/P_versus_NP_problem.

However, the important point that a known polynomial algorithm is more clearly bounded that a NP-Complete algorithm is fair enough.