Talk:Cobham's thesis

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)

"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)

I largely rewrote the section, taking all your points into consideration (despite the date on which you made them), but cutting out many specifics. In particular, changing the exponent and changing the base are the same thing, so I only discussed the exponent. I removed many of the specific examples because I felt they got in the way of the flow, although they were educational individually. The new section is in prose, and hopefully should be easier to read. It still reads as he said / she said, and it lacks any references (I didn't feel like citing my discussions with colleagues). Having killed a thousand of your favourite children, I now fully expect you to return the favour. Bhudson (talk) 00:42, 21 June 2008 (UTC)

Thank you for taking my points into consideration. I didn't even realize that it was April Fool's Day when I made those comments. I'm glad it was clear to you that they weren't an April Fool's joke. Now that you mention it, I agree that changing the exponent and changing the base are the same thing. But that probably won't be immediately obvious to readers, so perhaps we should specifically mention that fact in the article. I suppose that when I was writing, I gave more priority to clarity and educating the reader, instead of flow. However, I think some of the examples should go back in, because they'll make the article easier to understand for people who aren't familiar with computer science. I think we can include examples and still make it flow. Whether prose is easier to read than a list is a matter of personal preference. Also, I don't think there are any Wikipedia guidelines which specify that prose is preferred over lists. Correct me if I'm wrong. On the other hand, I suppose that when one reads an encyclopedia, they expect to see mostly paragraphs and not lists. I agree that references need to be added. Also, I noticed that your version doesn't include any discussion of the speed of hardware, while the previous version did. Did you think that point was invalid? I won't kill any of your children, but I might resurrect some of mine. :) Navigatr85 22:49, 8 July 2008 (UTC) —Preceding unsigned comment added by Navigatr85 (talk • contribs)

Since no one has responded with any objections, I'm going to add the information about hardware again, which Bhudson had deleted. Navigatr85 01:09, 26 April 2009 (UTC) —Preceding unsigned comment added by Navigatr85 (talk • contribs)

Although hardware certainly has an effect on performance, the examples added are ridiculous. The entire span of computers ever constructed is perhaps 10¹ instructions per second (with relays) to 10¹⁵ per second for a machine that has 1,000,000 fairly fast processors. So a machine with 10^{10,000,000,000,...(100 zeros)} instructions per second represents more than 10⁹⁸ times more progress than has been achieved to date. Furthermore, if you are willing to consider machines that violate the laws of physics as we know them, then no statement can be trusted. On the other end of the spectrum, a computer that executes 1 instruction every 5 years is roughly 10⁹ than any plausible implementation, and hence is a poor strawman as well. So if you want to make this argument, I think you should be bounded by the slowest plausible computer on one end, and the laws of physics as we understand them on the other. LouScheffer (talk) 02:46, 26 April 2009 (UTC)

Yes, my examples could be called ridiculous, but I think some of the other examples in the article are also ridiculous, and I think this ridiculousness is actually necessary to illustrate the point. One of the other examples given was an algorithm with a runtime of 10¹⁰⁰n, which is a ridiculous runtime. There is no natural problem whose best algorithm has that runtime. It is possible to imagine such a problem, but that problem would never occur in real life applications, and would not be useful at all. Similarly, it is possible to imagine a CPU that can do a googolplex operations in a second, but that CPU cannot be built in real life.

"Furthermore, if you are willing to consider machines that violate the laws of physics as we know them, then no statement can be trusted."

If you are willing to consider algorithms that violate the rules of what is useful in real life, then should I also say that none of your statements can be trusted? No, of course I shouldn't. The algorithm with a 10¹⁰⁰n runtime violates the rules of what is useful, but it's really more like a thought experiment, and it's not meant to be implemented on an actual computer. The purpose of the thought experiment is to show that there are exceptions to Cobham's rule. Similarly, the googolplex CPU is also a thought experiment, not meant to be implemented, and its purpose is also to show an exception to the rule. Also, I don't understand why a computer that executes 1 instruction every 5 years is not plausible. A clock rate in that range could be achieved, for example, by starting a tradition in which a person presses a button on a mechanical computer at the beginning of each Summer Olympics. Yes, I know that example is silly, and there would never be any reason to build such a thing. But, remember, an algorithm with a runtime of 10¹⁰⁰n is also silly, and there would never be any reason to write a program with that runtime. I don't think my examples should be bound by the real world, if there are already other examples that are not bound by the the real world.Navigatr85, 23:47, 19 August 2009 (UTC)

Also, I would like to add that I've changed my mind, and the information about hardware actually DOESN'T belong in the article. The reason it doesn't belong is simply because it's never been published before, and therefore there would be no way to have a citation for it. But I think the point is still completely valid. --Navigatr85, 09:44, 24 August 2009 (UTC)

Edmonds?

I remember reading something about this idea being due to Edmonds (of the matching algorithm, etc.) Does someone know more about this? Shreevatsa (talk) 23:02, 22 February 2009 (UTC)

I didn't remember I had left this question here, but it looks like I'll have to answer it myself. :-( I've added a couple of sources, but eventually they need to be rewritten describing who did what. Shreevatsa (talk) 01:22, 20 August 2009 (UTC)

I've also heard Edmonds mentioned in connection with this. Maybe in Garey and Johnson's book on NP-completeness. 75.57.242.120 (talk) 09:26, 30 March 2011 (UTC)

Cook lecture

Stephen Cook's Turing award lecture might be a useful reference for this article.[1] 75.57.242.120 (talk) 09:26, 30 March 2011 (UTC)

deleted text

I deleted a huge chunk of a basically useful and correct but misplaced text. Contrary to the opinion of the contributors (unreferenced, by the way), none of the below constitutes an objection. In fact, all of the below are approaches specifically developed to deal with inherent complexity of intractable problems -- essentially by tweaking the theoretical model of the real-world problem: put restrictions on the input, on the desired answer, etc. And by the way, simplex-algorithm is a popular but outdated example: it used to work best, but with recent advances polynomial-time algorithms are starting to beat it.

These are major issues. I can continue and proceed with nit-picking with some other blunders, but for now it is an overkill: the whole text mostly unreferenced.

---

The study of polynomial time approximation schemes considers families of polynomial-time algorithms where the exponent may depend on the desired error rate ε. For example, a PTAS algorithm may have runtime O(n^(1/ε)!). This has been a practical problem in the design of approximation algorithms, and was mitigated by the introduction of efficient and fully polynomial-time approximation schemes; see polynomial time approximation scheme for details.

The typical response to this objection is that in general, algorithms for computational problems that naturally occur in computer science and in other fields have neither enormous nor minuscule constants and exponents. Even when a polynomial-time algorithm has a large exponent, historically, other algorithms are subsequently developed that improve the exponent. Also, typically, when computers are finally able to solve problems of size n fast enough, users of computers ask them to solve problems of size n+1. These are all subjective statements.

Another objection is that Cobham's thesis only considers the worst-case inputs. Some NP-hard problems can be solved quite effectively on many of the large inputs that appear in practice; in particular, the travelling salesman problem and the boolean satisfiability problem can often be solved exactly even with input sizes in the tens or hundreds of thousands. Even though the same algorithms can be made to fail (take too long, use too much memory, or trigger an error condition) on some inputs, users may be content with only sometimes getting solutions.

In some cases, in fact, an algorithm that might require exponential time is the technique of choice because it only does so on highly contrived examples. The simplex method is one such example, typically preferred to polynomial-time algorithms for the same problem because it runs in linear time on most practical input even though it occasionally requires exponential time. Another example is the typechecking algorithm for Standard ML. The graph at the top of this article shows the empirical complexity for solving a particular subset of the knapsack problem, where the problem size increases but the individual numbers are bounded in size. For problems that fit this description, modern exponential-time algorithms demonstrate a quadratic growth over approximately 4 orders of magnitude on typical instances, which may be sufficient for many applications..

This is an example of an algorithm that runs in polynomial time if the size of their inputs is bounded. These problems are called fixed-parameter tractable and are said to be solvable in pseudo-polynomial time; they are studied by the subfield of parameterized complexity. For instance, the subset sum problem, the 0-1 knapsack problem and the multiple-choice subset-sum problem are all solvable in linear time, provided the weights and profits are bounded by a constant.

---

I leave it here, since it may be reused somewhere else. Max Longint (talk) 00:57, 7 October 2011 (UTC)

Moved long tagged OR section here

Policies mean something, or they do not. If the policy requiring verifiability and sourcing and those requiring that issues related to WP:OR exist, if they have meaning, they must have recourse in the event that they are unheeded. This action has been tagged for more than 7 years, and a little superficial checking shows it has been unsourced over a long period as well. It is placed here, someone can add the citations.

Objections

There are many lines of objection to Cobham's thesis. The thesis essentially states that "P" means "easy, fast, and practical," while "not in P" means "hard, slow, and impractical." But this is not always true. To begin with, it abstracts away some important variables that influence the runtime in practice:

• It ignores constant factors and lower-order terms.
• It ignores the size of the exponent. The time hierarchy theorem proves the existence of problems in P requiring arbitrarily large exponents.
• It ignores the typical size of the input.

All three are related, and are general complaints about analysis of algorithms, but they particularly apply to Cobham's thesis since it makes an explicit claim about practicality. Under Cobham's thesis, we are to call a problem for which the best algorithm takes 10¹⁰⁰n instructions feasible, and a problem with an algorithm that takes 2^{0.00001 n} infeasible—even though we could never solve an instance of size n=1 with the former algorithm, whereas we could solve an instance of the latter problem of size n=10⁶ without difficulty. As we saw, it takes a day on a typical modern machine to process 2ⁿ operations when n=46; this may be the size of inputs we have, and the amount of time we have to solve a typical problem, making the 2ⁿ-time algorithm feasible in practice on the inputs we have. Conversely, in fields where practical problems have millions of variables (such as Operations Research or Electronic Design Automation), even O(n³) algorithms are often impractical.

Until it is sourced, and verifiable, please do not place it back in the article. Please comply. Leprof 7272 (talk) 04:21, 1 February 2015 (UTC) Le Prof

Description of mpact is inadequate

At a cursory glance, the article fails to adequately describe the impact on the development of the computational complexity theory. Unfortunately I am an average software eng and lack the expertise to address this deficiency. Staszek Lem (talk) 17:48, 15 April 2016 (UTC)

Minor comment on "limitations" example

The Limitations section mentions that $2^{100}$ is considered as an infeasible amount of computation. While I was of this opinion until recent years, to my dismay it seems that currently the bitcoin community is running $\approx 2^{90}$ SHA-256 computations per year (not sure how many miners are around, not sure one could consider the mining community as a polynomially sized circuit, but still). I don't know how many bit-operations are required for each hash, but I think the example of $n^{100}$ for $n=2$ being infeasible may be getting out of date... Changing the exponent for 128 or 192 should do the trick (and if this becomes outdated, we'll have bigger cryptographic issues to deal with than the accuracy of an example on a wiki page 😬).

Agree. I did the same calculation and bitcoin mining is getting close. So I changed the example to n²⁰⁰, which should be a safe statement. LouScheffer (talk) 20:21, 22 July 2021 (UTC)