Talk:Cobham's thesis

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Stub	rated as Stub-Class on the assessment scale
Mid	rated as Mid-importance on the assessment scale

[edit] Approximation algorithms

I suggest at some point that we discuss the fact that some natural approximation algorithms have algorithms with very large exponents (this was the motivation for the definition of the class FPTAS). Not adding this right now since some expansion is coming. Dcoetzee 20:02, 10 March 2008 (UTC)

[edit] "Reasons" section and "Objections" section

I just added these two sections. This is part of the process of moving a section out of the P=NP article into this article. I'm busy right now, but later on I'll delete the info from the P=NP article, and I'll post some more thoughts here on the talk page. Navigatr85 00:39, 1 April 2008 (UTC)

OK, more thoughts: I not only copied things from the P=NP article, but also added some things. For some of the stuff I added, I'm not 100% sure about it. For example, I'm not totally sure that "Algorithms for problems that occur in practice typically have coefficients between 1/100 and 100." Also, Dcoetzee's post disproves my statement that polynomials with large exponents don't occur in "natural problems." And there are a few other things that I'm not 100% sure about. Also, I only have one citation. I guess I'm bending the rules of Wikipedia here. But please correct my mistakes, add citations, and continue to discuss here on the talk page. Thanks. Navigatr85 03:47, 1 April 2008 (UTC)

I think this is a good start - I think it's important to include something about the large exponents occurring in families of approximation algorithms. I also disagree strongly with the statement that "when we look at the running times of exponential algorithms that solve useful problems, almost all of them have a base of 2 or more." I've seen a number of problems with bases in the range of 1.2 to 1.8 (unfortunately I can't come up with one at the moment). I agree with the conclusion that bases very close to 1 are very unusual. Dcoetzee 17:39, 6 June 2008 (UTC)