Dear Fred #40,

fortunately or unfortunately, there is no universal algorithm for our brains to discover everything we would like to discover – like the correct fundamental laws of physics (although fine folks like Stephen Wolfram love to preserve some belief that such an automatization of thinking is possible in similar extreme ways).

We say that some creativity is needed. Trials and errors. At the same time, much of the progress is actually less mysterious than some “creativity” and boils down to high intelligence, hard work, and careful attachment to principles and methods that have worked and ways to generalize these methods.

Ignacio #34, thanks for this voice of reason, despite the “hard to deal with” bonus comment that you couldn’t avoid in that reasonable remark of yours. I back your comment.

Ks1 at #45, these questions depend on the definition of computation and algorithms. I am always using “computation” and “algorithm” in the sense of a sequence of some controllable steps with a totally accurately understood mathematical model (like binary operations in a microprocessor) that was probably designed by someone with a purpose and that may be exactly reproduced on “computers” of different constructions.

What Nature is doing when She is (probabilistically, because of quantum mechanics) evolving the Universe isn’t an algorithm in this sense. It isn’t computation. It is not composed of any sharply separated operations. The time is continuous and the laws of evolution aren’t exactly known to us, only in various approximations. And the differential equations or analogous laws governing the evolution (which are more general and more continuous than anything we call an “algorithm”) only work accurately in the right way on the “real” computer only, Nature itself.

Scott #35, first, the discussion isn’t about Mozart himself. (Mozart would say: My Prague folks understand me. So be sure that I am naturally among those who have more appreciation for Mozart than the people in Vienna and elsewhere LOL.) Of course that you just picked an example.

But you still meant that a great composer has a brain that is miraculous or qualitatively different from a seasoned listener to music who can recognize things and so on but who hasn’t made it as a great composer. I don’t believe that any such difference between great composers’ brains and other music fans’ brains is “qualitative” in a similar sense as P or non(P) problems are different. I don’t really believe in any “qualitative” differences between any people whatsoever – the belief that such differences are truly “qualitative” is what I would label as a misconception behind racism. And any animals are (more loosely) “qualitatively” analogous, too, to be more inclusive. The absence of “qualitative” differences in the inner working of the brains of anyone boils down to Darwin’s evolution, to our having common ancestors. This is clearly not an “equivalent” problem to “P=NP” but yes, I do think that your way of thinking about the origin of some special mental skills is in conflict with science (especially biology), too.

Concerning the discussion about the existence of “partial evidence”, Ignacio got it quite right. I don’t believe in partial evidence in discrete mathematics. That’s really the main reason why I think that such a frantic belief in assertions like “P != NP” is logically indefensible.

I have indeed “double standards” for mathematics and natural sciences (or any everyday questions grouped with natural sciences) but for a good reason. Mathematics *does* differ from natural sciences. All evidence in natural sciences is “partial” although the certainty may converge really, really close to 100%, like 99.999999999999%.

On the other hand, partial evidence in discrete mathematics just cannot exist. The P=NP discussion is effectively a discussion of the existence of some particular algorithms to solve e.g. SAT. We know that algorithms faster than “N factorial” do exist. We know that they may be sped up i.e. the function of N may be lowered. But we just don’t know how much lowered they may be. Some problems have polynomial solutions, others don’t, and we don’t know where SAT and the equivalent problems stand. We know it is NP but is it P?

In continuous mathematics that is more physics-wise, there may perhaps be partial evidence. So I think that there is partial evidence that the Riemann Hypothesis is right. The first “lots and lots of trillions” of the roots obey what they should obey and by some kind of “extrapolation” or (non-rigorous) “mathematical induction”, we may want to extrapolate. The existence of so many roots on the two axes only seems like a hint that there is a proof that all of them may belong to these axes, especially because “a priori”, there could be lots of roots away from them in the complex plane. But we don’t even know this rigorously and I do admit some doubts. The first root of Riemann zeta function that violates the Riemann Hypothesis could be the N-th root with some insanely high special value of N. It’s “unnatural” but we know that unnaturally high, extreme numbers sometimes or often do appear in rather natural and simple problems in mathematics.

So I admit that my bets about the Riemann Hypothesis are very far from 50-50, perhaps 99.9-0.1 in favor of its validity. But the analogous reasons for this asymmetry don’t exist and really can’t exist in the case of a problem about the existence of a single discrete structure – a particular algorithm solving a particular problem with some minimum expected speed – because no other problems in maths may be considered truly analogous to P=NP, so there is no way to extrapolate or guess based on the evidence. Any claim that P=NP must be “almost the same” as some other Yes/No question in maths that has already been answered is just a demagogy because all the other questions are substantially different for their answers to be uncorrelated, and the “analogy” may be equally well constructed with P=NP as well as P!=NP.

So I do think that the frantic belief that P cannot be NP is really irrational, boiling down to totally irrational beliefs such as your “great composers must have an unexplainable miracle in their brains that makes them different species than any mortals”, and that are partly motivated as an excuse for the fact that you (the algorithmic community) haven’t been able to find the fast enough algorithm for SAT even though it may very well exist. So it’s safer to invent an ideology that “it cannot be found at all” although you can’t prove it, either. But those who look at it rationally see that the odds are about 50-50.

Best wishes
Luboš