Talk:LibraryWithoutImplicitExportIsPolynomial - Revision history

Apidesign at 18:44, 25 December 2011

2011-12-25T18:44:02Z

←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-25T18:43:01Z

←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-25T18:39:22Z

←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-23T08:35:39Z

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.