tag:blogger.com,1999:blog-3722233.post113829817695831440..comments2023-03-27T02:45:06.501-05:00Comments on Computational Complexity: How Much are we effected by non-scientific criteria?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1138560078010172462006-01-29T12:41:00.000-06:002006-01-29T12:41:00.000-06:00Re: P vs NP a natural problem.The P vs NP question...Re: P vs NP a natural problem.<BR/><BR/><BR/>The P vs NP question (or things closely related to it) arose several times, in several different contexts. They came out of diverse technologies and cultures, not as a result of a single scientific subculture--that is one of the reasons why it is an important problem.<BR/><BR/>(A partial list:<BR/>1. Goedel's letter to von Neuman, suggesting that it would be important to know whether tautologies have short proofs.<BR/>This is NP=?co-NP, but it is closely related.<BR/><BR/>2. Many reductions among difficult combinatorial problems were known, and actively pursued in the context of 01 integer programming before the formal definition of the P vs NP problem.<BR/><BR/>3. The definitions of P and NP given by Edmonds arose in the context of trying to explain why algorithms that were too slow on the then existing computers were still valuable.<BR/><BR/>4. In the late 60s, early seventies there was a research agenda in the OR community to prove that NP intersect coNP = P, as the natural generalization of duality in Linear Programming and graph minimax theorems, or prove that the conjecture is false.)<BR/><BR/>I believe that the characteristic of natural and important problems is that they arise in several independent ways.<BR/><BR/>For example, if Newton was never born, we KNOW that we would still have Calculus, courtesy of Leibnitz.<BR/><BR/>There is no question in my mind that the underlying big question "How do we prove that a computation on a <I>general</I> model is hard?" is a fundamental one. P vs NP is important because it is a manifestation of it. I bet that a useful technique will change our ideas of what computation is, in the Kuhnian sense. That's why the question is important.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138549136469059962006-01-29T09:38:00.000-06:002006-01-29T09:38:00.000-06:00This seems to be a confusion of reality with the m...This seems to be a confusion of reality with the models we devise to explain reality. In philosophy this is called the error of reification.<BR/><BR/>When we move from one model to another model of reality we are not moving from one reality to another. The reality we attempt to model is the same reality. Only the model has changed. And we only change models if there are inadequacies in the older model and useful things we can do with the new model we could not do with the old. <BR/><BR/>We should also be aware that newer models of reality are not necessarily better models. The new model of Eugenics in the early part of the 20th century was not a better model scientifically as it allowed some political forces to get away with murder literally. It was also false and a poor scientific model that was eventually replaced by a genetic model. <BR/><BR/>I could level similar criticism toward the string "theory" of physics as it has yet to come up with a testable hypothesis and thus is certainly NOT a theory. People, who otherwise have good sense, want the string "theory" to be correct so badly they are opening themselves to ridicule. <BR/><BR/>Somehow science can now be done with just mathematical a priori reasoning and no laboratory or testing is needed? Some people are making silly assumptions string theory is true and thus the need for verification has suddenly been eliminated in science. This is no different than the fundamentalists' claim that belief is all we need to make truth. And THAT is definitely a very poor model of reality.<BR/><BR/>Completeness and consistency of any mathematical system by themselves tell us nothing about the world. Only testing can verify how close our models are to reality.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138357880758507412006-01-27T04:31:00.000-06:002006-01-27T04:31:00.000-06:00You claim to be describing the Kuhnian philosophy,...You claim to be describing the Kuhnian philosophy, but what you have described seems quite Lakatosian to me. The central question is:<BR/><BR/>When a scientist chooses to switch from one paradigm to another, can s/he be said to be doing so for RATIONAL criteria? That is, although people are affected by a variety of outside influences, the "correct" choice will be made by the majority in the long run.<BR/><BR/>By correct I mean, can we say, at least in hindsight, that the new paradigm is OBJECTIVELY more correct, by some specified criteria, than the old one? An example of such a criterion might be "a closer approximation to reality" or "more empirically adequate" (at least for scientific theories - the situation in Math is a bit different). If you think so, then you are a Lakatosian and if not then you are a Kuhnian.<BR/><BR/>This is related to whether one accepts Kuhn's notion of incomensurability or not, e.g. is the meaning of "mass" in Newtonian and Relativistic mechanics so different that we can't compare them objectively, or is the Newtonain concept really subsumed by the Relativistic one, as most physicists believe.<BR/><BR/>The Kuhnian view does seem to me to lead to relativism about science and the whole postmodern attack. Kuhn might have rejected this, but I don't think he managed to argue convincingly against it in his book.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138326347601737232006-01-26T19:45:00.000-06:002006-01-26T19:45:00.000-06:00I am surprised you didn't list under non-scientifi...I am surprised you didn't list under non-scientific criteria: Where the money isAnonymousnoreply@blogger.com