Could another characterization of NP-hard problems be that their naive algorithmic solution (e.g. permutations) is factorial; whereas, a dynamic programming algorithm is exponential?
in [Theory]
|
Prev: If - this statement is used to open an exact proof p = np, if this is true or false, do this.
Next: randomized quicksort: probability of two elements comparison?
From: Casey Hawthorne on 4 May 2010 12:10 Could another characterization of NP-hard problems be that their naive algorithmic solution (e.g. permutations) is factorial; whereas, a dynamic programming algorithm is exponential? e.g. symmetric metric TSP using naive permutations is O(n!), whereas using using dynamic programming TSP it is O((n^2)(2^n)). -- Regards, Casey
From: Daniel A. Jimenez on 4 May 2010 14:52 In article <iff0u55vd0cvnet7a7ufu9rtg289b7tvss(a)4ax.com>, Casey Hawthorne <caseyhHAMMER_TIME(a)istar.ca> wrote: >Could another characterization of NP-hard problems be that their naive >algorithmic solution (e.g. permutations) is factorial; whereas, a >dynamic programming algorithm is exponential? >e.g. symmetric metric TSP using naive permutations is O(n!), whereas >using using dynamic programming TSP it is O((n^2)(2^n)). No. The naive algorithm for SAT is "only" O(n 2^n). -- Daniel Jimenez djimenez(a)cs.utexas.edu "I've so much music in my head" -- Maurice Ravel, shortly before his death. " " -- John Cage
From: tchow on 4 May 2010 18:41 In article <iff0u55vd0cvnet7a7ufu9rtg289b7tvss(a)4ax.com>, Casey Hawthorne <caseyhHAMMER_TIME(a)istar.ca> wrote: >Could another characterization of NP-hard problems be that their naive >algorithmic solution (e.g. permutations) is factorial; whereas, a >dynamic programming algorithm is exponential? >e.g. symmetric metric TSP using naive permutations is O(n!), whereas >using using dynamic programming TSP it is O((n^2)(2^n)). Nice thought, but I don't think so. Take satisfiability, the canonical NP-complete problem. I would say that the naive solution is to try all possible variable assignments, which takes exponential time, and not factorial time. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Torben �gidius Mogensen on 5 May 2010 09:28
tchow(a)lsa.umich.edu writes: > In article <iff0u55vd0cvnet7a7ufu9rtg289b7tvss(a)4ax.com>, > Casey Hawthorne <caseyhHAMMER_TIME(a)istar.ca> wrote: >>Could another characterization of NP-hard problems be that their naive >>algorithmic solution (e.g. permutations) is factorial; whereas, a >>dynamic programming algorithm is exponential? > > Nice thought, but I don't think so. Take satisfiability, the canonical > NP-complete problem. I would say that the naive solution is to try all > possible variable assignments, which takes exponential time, and not > factorial time. Another example is k-colouring a graph: The naive approach is to try all N^k colour combinations, which is also exponential. But I think you (with a suitably vague notion of "simple") can say the following: If there is no simple sub-exponential way to bring the number of potential solutions down to less than exponential, but you in polynomial time can determine which of two potential solutions is best (or if they are equally good), then the problem of finding an optimal solution is in NP. If P!=NP, then the word "simple" can be eliminated, but if P=NP, then there _will_ be a sub-exponential way to reduce the number of potential solutions. So if you want to avoid showing that a known NP problem can be reduced to your problem, I don't think you can avoid vagueness in statements like the above. Torben |