Wednesday, February 19, 2014 ... Français/Deutsch/Español/Česky/Japanese/Related posts from blogosphere

Erdös discrepancy conjecture proved for \(C=2\)

...but the proof is unreadable for humans...

As Mr Synchlavier informed me, a week ago, Boris Konev and Alexei Lisitsa of Liverpool released their new 8-page preprint

A SAT Attack on the Erdös Discrepancy Conjecture

Nude Socialist, IO9
They finally solved the Erdös discrepancy problem (1932).

Yes, it's the same Erdös who sits at the center of the "collaboration distance" between researchers; my Erdös number is four but of course e.g. my Hawking number is two. Erdös would offer $500 for a solution which wasn't spectacularly generous relatively to the awards you may win these days. What is the problem?




For any infinite \(\pm 1\) sequence i.e. \(\langle x_1,x_2,\dots \rangle \) with \(x_i^2=1\) and any integer \(C\in\ZZ\), there exist integers \(k,d\in\ZZ\) such that\[

\abs{ \sum_{i=1}^k x_{id} } \gt C

\] Yes, the subscript really means that we are summing every \(d\)-th element in the sequence. The term "discrepancy" pretty much means the maximum of the left hand side above assuming a fixed maximum \(id\). Note that for a random \(\pm 1\) sequence, the discrepancy grows more or less as \(\sqrt{id}\). You need to study "more carefully balanced" – but not periodic – \(\pm 1\) sequences if you want to have a chance to reduce the discrepancy to a small finite number (and to disprove the conjecture).

Is the claim above true or not? For \(C=1\), it is a proven fact and a human being has found it. It is simply impossible for sequences to be so balanced yet aperiodic that the discrepancy remains at most one.




For \(C=2\), people would only dare to attack the problem with computers but they only got to sequences of length 1124 of discrepancy 2. The two Russian Britons would find a sequence of length 1160 and discrepancy 2 while they would prove that all sequences of length 1161 have discrepancies greater than 2.

Their proof only has one feature that some people could consider a problem: it was computer-generated, based on the state-of-the-art SAT solver, and its length rivals the total size of all pages on the Wikipedia. Such a proof is clearly unreadable by any human being except for Edward Witten.

Do I have a problem with that? Not really. I would probably "prefer" a proof I could read and verify with my neurons (especially if I could enjoy it). On the other hand, despite all the advantages, I think that my brain is a pile of unreliable biological junk and silicon is more trustworthy when it comes to the verification of some excessive combinatorial games. Well, I haven't even verified the computer code and data needed to prove the Erdös discrepancy problem but that's a problem that other human beings will hopefully overcome. My main reason not to care is that there is no qualitative difference between proofs that may be followed without a computer and those that make the use of silicon a good idea.

They haven't proven the full Erdös problem so years or centuries of extra work along with multi-billion investments into mathematics research and computers will be needed for them (or the people in the year 2600) to win $500 from Erdös' heirs. They have solved the case \(C=2\) and sketched some partial results for \(C=3\). The original problem was making a statement about arbitrarily high values of \(C\), i.e. it was stating that the discrepancy is pretty much unbounded from above.

It is sort of remarkable that the critical sequences that matter for as low a number as \(C=2\) have length 1160 or 1161. But mathematics is full of similar problems that generate "huge numbers" already for very small values of the parameters. I have made the same point in May 2013 when I argued that the widely held belief \(P\neq NP\) inequality isn't necessarily true.

(Update: In March 2014, complexity theorist Prof Dick Lipton of Georgia Tech made pretty much the same points about the impact of this Erdös discrepancy work on \(P=NP\) as I did here before him.)

The newest result about the Erdös discrepancy problem is just another piece of evidence that I may be right and folks like Scott Aaronson or Boaz Barak might be extraordinarily naive – in their very field of algorithmic complexity. Let me remind you that they believe that \(P\) must be different from \(NP\), otherwise everyone who could listen to music would be as creative as Mozart – a slogan they obviously mean rather seriously.

I am saying that \(P\) may very well be the same class of problems as \(NP\). It means that every problem dependent on a parameter \(N\in\ZZ\) whose solution may be verified in a polynomial time, \(O(N^\ell)\), may also be solved in a polynomial time, \(O(N^m)\).

This wouldn't necessarily mean that every listener of music is a Mozart because the work and memory needed to find a solution ("composer's creative work") could contain one whole Wikipedia server for every byte of the verification of a solution ("hobby of a mediocre music fan"). The proofs may be vastly longer and more laborious than their verifications – and this very Erdös example shows that huge ratios like to appear often and naturally.

So both "composition" and "listening" to the music may be "qualitatively comparably difficult" in the sense that both of them may be polynomial. But the practical, quantitative, numerical difference between them – in the amount of the required brute force – may still be gigantic. This conclusion compatible with \(P=NP\) is perfectly conceivable, if you think about it, but this possibility is an inconvenient truth for Scott Aaronson and lots of other complexity theorists who just don't want to admit that their decades-long obsession with the separation of the problems to "polynomial" and "non-polynomial" ones may be a rather misguided, superficial, and useless idea.

They have first decided that they should be religiously obsessed with this arbitrary split, and then they are adjusting their beliefs about everything unknown to agree with the dogmas – a typical unscientific approach. Of course, one needs a rigorous proof of \(P=NP\) to actually demonstrate that their beliefs were not only unsupported by the available evidence but actually wrong.

Add to del.icio.us Digg this Add to reddit

snail feedback (43) :


reader lucretius said...

Anna, like many others, seems to believe that any money not collected by a government disappears into a black hole or at least is misused for indecent pleasure of the undeserving wealthy. Hence people who “don’t pay taxes anywhere” are evil or at least worthless and a world government is needed to keep them in check. Her analysis of the banks and “big industries” squeezing the middle class is almost exactly the same as Marx’s analysis of the way capitalism will “inevitably” lead to the total pauperization of the middle class, the only difference being that Marx attempted to give an economic justification (in terms of the capitalist’s need to extract “surplus value” from the worker until the worker receives only as much as is necessary for his physical survival), while Ann has no argument at all and probably thinks that capitalists do this because of their innate selfishness. It is not quite clear if she thinks (like Marx) that capitalists “have to do this” because of the nature of capitalism, or whether it because but guys only become capitalists and good people do more noble things (like, presumably, experimental physics).

In any case, the world “globalization” is a modern synonym for “capitalism” in exactly the same way as “zionist” is actually a de facto synonym for Jew. In both cases, in principle, one can be one but not the other, but in practice it serves as a “respectable” way of being the other.

Globalization is actually nothing but capitalism and like capitalism it does cause upheaval and disturbance but at the same time it is the engine of economic growth, prosperity and, as a side effect, scientific progress. The modern anti-globalist is exactly the anti-capitalist of old, whether he or she understands that or not.


reader MacDuff said...

Hey Lubos, sry for off-topic but can you comment somehow on this page http://hixgrid.de/pg/photos/album/13985/group-model-string-theory-development-by-mark-aaron-simpson
What excatly do these pictures show? And is it accurate?
Greets


reader Gene Day said...

Really, Lubos, your brain is a pile of unreliable biological junk?


Hardly.


reader Luboš Motl said...

Hi, they show art, a pretty nice one, that is described as being "string theory" or "models" or "atomic" etc. because the author is both an artist and a crackpot.

It's not hard to see that the author doesn't know what he's talking about. Misspelled words such as "guage" (gauge) and "Calibi" (Calabi) may be an easy hint.


reader Luboš Motl said...

Thanks, but I do share Sheldon Cooper's view that it would be nice if one could migrate the mind from the imperfect, fragile biological body to something more technologically robust. And that includes the brain, at least the brute force aspects of the organ which are still affected by the imperfections of the remainder of the biological body.


reader MacDuff said...

Calibi ;D haha ok I see, thx for reply always good to hear your opinion on such things.


reader Sage Basil said...

to me, a problem is in NP if there is no algorithm qualitatively better than guess-and-check. For example, Sudoku; it's just boring.


reader Uncle Al said...

The 1776 Insurrection protested a penny tax on tea. The 1791 Whiskey Rebellion had the new government slaughtering farmers who distilled without paying production taxes. Dodi Fayed's main squeeze Princess Di was famed for condemning Third World landmines massively vended by Fayed's uncle Adnan Kashoggi.


Preferably.


reader Uncle Al said...

http://hixgrid.de/pg/photos/view/13991/model-for-atomic-neon

The model for "atomic neon" is empirically falsified by a neon light's emission spectrum and the gas' specific heat. One need be mighty stupid to screw up an inert gas (or be Neil Bartlett who screwed up Xe + PtF_6).


reader anna v said...

You are really on a roll with contradicting statements:"Hence people who “don’t pay taxes anywhere” are evil or at least
worthless and a world government is needed to keep them in check." and "the world “globalization” is a modern synonym for “capitalism”" .


I am making an observation: If nobody payed taxes there would be no stability in countries. . When foreign exchanges was hard to come by sovereignity of countries could be kept.



Now that the frontiers are full of holes there are people, the UN among them, pushing for world government ( tje farce of global warming one of their tools) .



When all industry will end up in China and India the industrialists will still have their money . The unemployed in the countries that lost their industries, and this is happening in Europe , are pushed to minimum wage jobs. This is a fact, not a prediction. Withot industries the tax base is smaller, the country poorer.



The US is still printing money and has a huge dept to China but is slowly loosing industries too.


If I make a prediction it is that something has to give. We live in interesting times.


reader Luboš Motl said...

Dear Scott, my usage of that example may be amusing, but it's also vastly more quantitative and serious than your comparisons of P or NP problems with Mozart's compositions and their audiences.


reader lucretius said...

I hope you are joking but if so we have a very different sense of humour.

Have you ever seriously thought for one second that President Xi Jinping and his comrades will accept a "world government", unless, of course, they are it? Exactly the same applies to Gospodin Putin.



Clever people like yourself have been hoping for or alternatively worrying about "world government", the "Elders of Zion", "black helicopters", The Queen of England (especially Mr LaRouche whose views seem to much yours perfectly) whose etc., for about a hundred years now, and still there is no sight of it. Well, as for me, quite honestly, I would rather be governed by the Chinese or Indians who are intelligent and hard working people than the Greeks, who first binged on German money and now call them Nazis and whine about the loss of "sovereignty".
And by the way, if you think the Chinese and the Indians are going to "take over", why you can still buy their shares. I have been doing so myself so of of course I am now rooting for them...


reader Scott Aaronson said...

"Your comment is interesting but it's still true that you're just rationalizing your preconceptions"?? Man, I was expecting a meatier response -- especially from our dear host LM, one of the least self-aware preconception-rationalizers on the planet. ;)


Look, I apologize for the Mozart thing. Out of all the hundreds of examples, analogies, etc. that I've used in trying to explain P and NP, it was one of the least careful, so naturally it's the one Wikipedia quotes. :-) But even so, it's not hard to fix it. Here's a more careful formulation, which I'm happy to stand behind:


If P=NP and moreover the algorithm were efficient in practice, then it would be fair to say that "creativity could be automated," in any situation where the fruits of creativity could be mechanically checked. So for example, if you could write an efficient program that recognized Mozart-quality symphonies when given them, then that program could also be used to generate such symphonies. The one task would be no harder than the other. As a consequence, I'd say that the world would indeed be a very different place than we normally imagine it to be.


reader Michael Gersh said...

Sorry guys. America will win it all! Or not, but a guy can dream.


reader Michael Gersh said...

As an American, I should remind you that it is in our nature to win. Can't exactly say why, but it IS what we do...


reader Michael Gersh said...

It has been shown that the compliance cost of corporate tax exceeds the tax paid. In other words, the accountants and lawyers get more than the government. As an unrepentant capitalist, I like it that way.


reader Werdna said...

Yes. A lot of people say that the money spent on trying to keep our tax liabilities as low as we can is "wasted."

Well, one could as well say that money spent on locks, home security systems, etc. is wasted. And it would be wasted if there were no crime.


reader anna v said...

You are being offensive once again. The Germans drank the life blood of Greece and thousands of people died of starvation during the occupation and have still not given back the gold they borrowed from the bank of Greece then.

The money they improvidently borrowed during the fat cow years was borrowed in your famous capitalist markets which have no checks and balances of stupidity except the final bankruptcy. The huge amount lent by the EU and the international fund since 2009 came instead of letting us declare bankruptcy, so the EU countries and the people in the know could unload themselves from toxic greek bonds. We owe now much more than we did in 2009 .These bonds are now in the central EU bank, and all the new money added is so that they can be bought back in full value when maturing. Germany has gained up to 75 billion euro since then .

I had said then that we should have defaulted and followd the market rules.going back to the drachma. The EU powers that be ( call meGermany) took this decision of repaying debt with more debt in order to save the eurozone, I believe.

You see that the market rules are followed only when the ones holding the capital/market are involved. They are bent as much as needed when the capital itself should have followed them.

Humans are humans out for number one, whether collectively or individually most of the time. Unfortunately we had as socialist government at the time we should have declared bankruptcy.

As for the world government which started all this idiocy of markets and capitalism in this interchange , I neither wish it nor abhor the idea. It is the path I am watching the way one watches the path of the river. If you think that the whole global warming scarecrow has nothing to do with a path the world is being pushed towards fine with me. I look at the current snapshot and that is what I see.. The future will tell. A fanatic religious type adherence to any political system obscures the facts.

BTW The Chinese might love a global government in a hundred years time. They already are governing one billion people.


reader Luboš Motl said...

No, Scott, you're still totally incapable of distinguishing what is known and what is not known.


First of all, this Erdös discrepancy problem example and many others *show* that an algorithm or a solution that may be short or fast in principle often *isn't* short or fast in practice.


Second, even if you could prove the demonstrably invalid assertion that algorithms fast in principle are also fast in practice, it would still not contradict anything.


The world with P=NP would not be a different place than *I* imagine it to be because this may very well be our world and I am - much like all rational people - agnostic about questions that are just not known.


It's perfectly plausible that in our world, there may exist an instruction manual of size WikipediaSize^6 that in the time "10^{300}" converts every verification algorithm to an algorithm to solve the same problem that is in principle at most polynomially slowed down.


The very formulation of yours about "we imagine the world to be one way or another" indicates that you just can't separate yourself from the group think, irrational and indefensible assumptions, from the cheap reasoning of a mediocre human in a mob.


I am just not thinking in this way, I am a rational person.


reader Luboš Motl said...

LOL, congratulations. It's the strongest team USA on Olympics, ever. Paradoxically enough, it's also a socialist-style ice-hockey team, avoiding superstars in favor of some discipline a cooperation.


The score 5-2 doesn't correspond to the actual balance of power on the ice which was almost symmetric but in the whole tournament, U.S. is just playing great and I won't be shocked if it is the champion.


reader Smoking Frog said...

Sudoku isn't "guess-and-check." The numbers that belong in a very few of the empty cells are obvious, and the rest are derivable. What's "boring" about Sudoku is that apparently there's no way to reduce the problem to something simpler.


reader Eugene S said...

Dear Luboš, what exactly do you mean when you write, "not imagining Mozart's creativity to be qualitatively different from other musicians'"? If any composer is qualitatively different, surely it is Mozart. And neither musicology nor any quantitative science has been able to analyze the secret of this difference, certainly not to the extent of producing a recipe or algorithm for composing the music Mozart would have composed had he lived longer. In some sense, it's a similar mystery to how famous mathematicians have either plucked new math from some Platonic realm or their creativity was so strong as to accomplish what seemed like it. And I see a parallel between the "unreasonable effectiveness of mathematics" in our physical world and the ability of Mozart's music to touch so many humans in their deepest core and ennoble them, even if only temporarily.

If you are truly agnostic, shouldn't you concede the possibility that some of these mysteries will never be solved, not because of our feeble powers of analysis, but as a matter of principle, because there are things for which quantitative science is an insufficient instrument to enable understanding?



P.S.: Don't let the ballot-box stuffing from Scott's fans annoy you. They're like the U.S. Army, whereas TRF is like "the few... the proud... the Marines" ;)


reader lucretius said...

Well, you have worn me out Anna. I think discussing politics with you is about as productive as discussing homeopathy. I know, the German wealth was all stolen from the Greeks and should be returned and now they are conspiring with the Chinks, after all they seem to be doing very well trading with China. e.g.
http://www.bloomberg.com/news/2011-04-06/germany-s-future-rising-in-east-as-exports-to-china-eclipse-u-s-.html



But honestly, you need not worry about the Yellow Peril in a hundred years time sine by then you are much more likely to be a small part of the New Ottoman Empire.


reader lucretius said...

I agree and would further say that the entire Mozart “example” in this context is fundamentally misconceived because musical creativeness is not primarily about complexity (in the sense of computational complexity the music of the Renaissance, e.g. Tallis’s “ Spem in Alium” http://en.wikipedia.org/wiki/Spem_in_alium is probably more complex than any composition of Mozart. )

David Cope has written a computer program that writes music in Mozart’s (and Bach’s) style. It is quite difficult for a casual listener to distinguish music composed by the program from lesser works of Mozart (of course real experts, and even myself, know practically all Mozart works by heart so it is easy to tell that a symphony produced by Cope’s program is not one of them. It’s much harder to tell that it is not some unknown symphony by young Mozart).

As for the great works by Mozart, they are completely different, but it is certainly not because of their computational complexity. A relatively simple work, like one of my favourites, the string trio K563:

http://www.youtube.com/watch?v=kNaVMvOSMUc

is, in my opinion, a superior work to most of the symphonies, which probably have greater complexity but lesser “creativity”.

To a large extent, the same sort of thing applies to a lot of mathematics. The most beautiful proofs are usually not the most “complex” ones. In fact, Erdős himself used to refer to “the Book” in which God keeps the perfect proofs. Martin Aigner and Gunter Ziegler published some of these proofs (“Proofs from the Book”, Springer 1998)

in what was meant as a 85th birthday present for Erdős who unfortunately died just before. As anyone can check for onself, it would be difficult to claim that any of these proofs are “complex” in any sense that computer science understands.


reader Eugene S said...

Yes, but we love the Greeks so we will finance the 22nd-century War of Greek Independence. They will default on that loan just as they did on the previous ones, but that's okay. After all, we love the Greeks!


reader Luboš Motl said...

Dear Eugene, Mozart was great but sorry, he can't change my opinions/knowledge about the origin of species.

His brain qualitatively worked just like Beethoven's or Lady Gaga's brain. There can't be a qualitative difference.


Turning Mozart into a qualitatively different God may be a fun part of the folklore but sorry, I just don't buy such things.


After all, I have been influenced by many refined people who considered Beethoven to be a superior composer relatively to Mozart, so not only they would disagree that Mozart was qualitatively different from other composers; they wouldn't put him at the top at all.


I think that this "qualitative vs quantitative" difference is a theme that has been constantly influenced by progress in science, especially theoretical physics, and the evolution was that everything that used to look "qualitatively different" was found to be a different manifestation of the same thing, so all the differences were reduced either to quantitative differences or to different solutions or different interpretations of the same underlying laws.


For this reason, I think that the beliefs in "Mozart's being totally qualitatively different from anyone else" contradicts some of the most universal lessons we have learned from science. None of these things means that I don't admire Mozart or love his music. But yes, it is true that I view every kind of religious worshiping of this kind to be silly. It's true for Mozart, Einstein, or anyone else who is sometimes promoted to a god or God.


reader Eugene S said...

It's not that I elevate Mozart to a status above all other composers. Mozart and Beethoven both belong in the pantheon, that's beyond argument. Rather, I feel that the inexplicable genius (which, as lucretius noted, is not a function of complexity; likewise, the two-headed genius of Lennon/McCartney is not complex; as with Mozart, the "black-on-white" (chord progressions, melodies, counterpoint) is simple) of Mozart teaches us humility in what we may presume to know about humanity and creativity, in which to varying extents all of us share.

Did you not call yourself a Platonist the other day? Where is that Platonic realm located? Will it ever be found, or could it be that it will forever remain mysterious? And if my memory is not playing tricks on me, I think you even referred to yourself on this weblog as "divinely inspired" during the time you were working on your "matrix M theory".


reader Luboš Motl said...

Dear Eugene, I sometimes use terms like "God" and "divine inspiration" as well but I mean it as some kind of poetry to convey some feelings. But as a rational person, I don't really believe that poetry or feelings correctly describe how things actually work.


As a Platonist, I believe that the precious mathematical structures exist independently of the real world - that also means outside Mozart's or Beethoven's minds. It is not clear to me how you wanted to correlated Platonism with this discussion about Mozart's divine status but for me, Platonism is close to the paradigm that no human and no real-world object has a divine status.


Otherwise, in my opinion, you seem to be making way too many assumptions that you want to impose on the reader in your comment. Like "inexplicable genius". Well, I am open-minded - and leaning towards Yes - when it comes to the question whether the (Mozart's etc.) genius is explicable.


And while I also love classical music more than 90% people do, I won't jump on the bandwagon of automatically assuming that every 20th century composition has to be inferior. I don't really believe it. Perhaps the Beatles created simple enough songs but they were ingenious in their own right, and I think that one could find 20th century composers for whom the character of ingenuity would be very similar to Mozart's.


There are different directions in which music may be developed. According to the preferred direction, even the likes of Vangelis or Jaroslav Ježek or Karel Svoboda etc. could be viewed as Beethoven's or Mozart's true counterparts. They will never ring quite the same but I don't think it's purely due to the merit.It's due to the fact that the divine status of Mozart etc. has been incorporated into our culture and way how children are brought up etc. At that time, the number of composers was also much lower than today, so they were more special relatively speaking, but I don't think it means that they were necessarily objectively superior relatively to all contemporary composers etc.


reader Eugene S said...

Perhaps the Beatles created simple enough songs but they were ingenious in their own right, and I think that one could find 20th century composers for whom the character of ingenuity would be very similar to Mozart's.

Absolutely, yes.

Vangelis? Now you're trolling ;)


seem to be making way too many assumptions that you want to impose on
the reader in your comment but whose validity is questionable

Perhaps. It would not be the first time. I will try to improve my signal-to-noise ratio by being more cautious.


reader Luboš Motl said...

Dear Eugene, sorry for what seemed like trolling.

It's completely plausible that I placed Vangelis that high because his "To the Unknown Man" was used as the theme song for the popular astro/physics TV program by Jiří Grygar and Vladiimír Železný, Windows to the Universe are Wide Open, that I would watch as a kid around 1980.

http://www.youtube.com/watch?v=Z4bO7b4FaJI

http://www.youtube.com/results?search_type=search_videos&search_query=okna+vesm%C3%ADry+doko%C5%99%C3%A1n&search_sort=relevance&search_category=0&page=


reader anna v said...

1) you have the cart before the horse. Germans took all the greek wealth in the 1940's, and for the gold they even signed a loan paper. The present wealth of Germany is due to the foresight o the US which unilaterally decided to wipe off most of the war reparations being afraid that a Germany in misery was much more dangerous to the world ( as happened after WWI) tjhen Germany in affluence. As we see now there are only economic wars and economic one up manship within the EU at that, so it was a good decision overall.

If you take the trouble to look at te gene pool of the Tyrks it is more than 80% Greek on the coasts and Armenian Asyrian etc inland. The invaders and dominators were mongolian and there is scarcely a mongolic fold to be seen in the coastal Turks. It is Islam that is the problem and not only for Greece because there is an insidious invasion going on with all those economic and political refugees infiltrating the EU through differences in economic pressure from all the islamic countries of africa and the middle east. I foresee it will be a common to Europe problem, as it was in the middle ages. I could happen that Islam mellows the way christianity has and the empires will be only econoic ones. At the moment Greece is betting on the German one.


reader Eugene S said...

I will watch those videos later, it sounds like they could be fun (although perhaps not as much fun as the dinosaur science show that always ended in the line "We need a new Timmy".)

By the way, I wish to commend you on your restraint in not rising to the bait of a certain physics blogger whose latest piece on "foundations of quantum mechanics" seems designed to provoke an angry reaction from you without mentioning you by name. Apparently she figures, well Dr. M has already called me all the names in the book so he can't hurt me anymore but if he links to me I get traffic and my google ranking goes up so I will poke him with a stick and see if he responds :/


reader Luboš Motl said...

Dear Eugene, do you speak Czech!? Otherwise the videos might be of limited value, except for Vangelis' music and Saudek's cartoons. ;-)


I really couldn't find the *** blogger who would call you names and talked about foundations of QM.


reader Scott Aaronson said...

Quick clarification: I ALSO don't think Mozart had supernatural powers, so there's no need to argue this point. He figured in my example only as "a famous composer." If P=NP and the algorithm were efficient in practice, it would also be true that the ability to write a program to efficiently recognize "the sort of songs that Ke$ha or Justin Bieber or Lady Gaga sing" would imply the ability to generate more such songs for yourself. Though admittedly, that might be the case even if P!=NP. :-)


Also, "sockpuppets" remains a strange term for "mostly right-wing Lubos fans, some of whom are apparently nevertheless persuaded by my superior arguments." ;-D These are YOUR readers -- I haven't sent a single soul over here.


reader Luboš Motl said...

Dear Scott, if you hover your mouse over the upvote button, you will be told that it's many "guests". If it were a particular user like Eugene S, there would be his nickname.


So to say the least, they are not recognizable active users of TRF.


Incidentally, it's debatable whether most TRF visitors are right-wing. I don't have evidence in either way. Politically active leftwingers are much more likely to get banned, of course. At any rate, I don't see any recognizable correlation between P=NP and the political left wing or right wing.


reader lucretius said...

As I pointed out below, David Cope (http://en.wikipedia.org/wiki/David_Cope ) has written a program that writes music in the style of Mozart and Bach.


So please, get someone to perform the following test : play (chosen at random) a less known early symphony by Mozart like, say, KV97 or KV98 (which may not even be by Mozart ;-)) and then one of the pieces composed by Cope’s program, then guess who wrote which. If you fail, then please recommend me for a Millenium Prize since, according to you (and Wikipedia) that would constitute a proof that P=NP.


reader Sage Basil said...

there does not currently exist an algorithm qualitatively better than guess and check. It is as derivable as the satisfiability of a logical statement, i.e. it belongs to the NP class.

In a very real sense, there is no problem that is "simpler" that logical satisfiability. Defining simplicity of a problem by the performance of the best algorithm to solve it is the kind of thing a student would do.


reader Sage Basil said...

Dr. Aaronson, with all due respect, the reason it is irresponsible to compare things to Mozart is people have all kinds of associations for musical genius that your analogy evokes but does not use.


If we try to take your analogy seriously, it is clearly false. It currently takes a human brain to appreciate all the types of musical genius; Mozart had a human brain. Dr. Motl has pointed this out.


The only reason for a scientist to ever talk about Mozart is if he wants to be quoted in Wikipedia.


reader Pavel Krapivsky said...

Dear Eugene, you will probably perform much better than most if you'll try to distinguish Mozart from Salieri using this quiz
http://reverent.org/mozart_or_salieri.html
By the way, the webpage
http://reverent.org/
contains tons of other amusing quizzes, like distinguishing masterpieces of minimalism from cheap furniture, etc.


reader chris said...

The debate on whether a qualitative difference in creativity exists reminds me of Mark Kac's famous distinction between "ordinary" and "magical" geniuses. He put Bethe in the first category, Feynman in the second. According to Kac, an ordinary genius is someone we could imagine ourselves being like, if only we could think a hundred or thousand times faster. A magical genius is someone we cannot imagine ourselves being like, since their thinking is so different.

Feynman and Einstein, for example, were not extraordinary in their rapidity of thought, but in their ability to think "outside the box", i.e., qualitatively differently.


reader Luboš Motl said...

Concerning Scott's assertions below that "this result has no particular bearing on P vs NP", well, his Georgia Tech colleague (complexity theory) Prof Dick Lipton

http://rjlipton.wordpress.com/2014/02/28/practically-pnp/



obviously disagrees with Scott - and instead, agrees with me completely. And I have the priority. ;-)


reader vznvzn said...

beat ya to it! see also great moments in empirical/experimental math/TCS research, breakthrough SAT induction idea ... so you think the P=?NP question is no big deal eh? have you written anything on your opinion of the $1M award associated with it? is $1M no big deal to you? :p


reader Luboš Motl said...

LOL, I don't know how to solve. Moreover, I consider the Riemann Hypothesis by far the deepest problem among the seven, so maybe the money isn't the main thing that affects what I am thinking about.


To prove or disprove P=NP is still probably very difficult.


The problems related to hydrodynamics, QCD, and some others could be optimally addressed to sophisticated secretaries. I find it totally plausible that the person who will win the $1 million prize in those cases will write something that won't really contain anything conceptually new or interesting because the right answers may already be known, including their intuition, and someone may just write it down a bit more rigorously so that it passes.


RH is different.