Slashdot Mirror

A German man -- Norbert Blum -- who claimed that P is not equal to NP is seeing several challenges to his solution. From a report: Numerous mathematicians have begun to raise questions about whether the German mathematician solved it at all. Since Blum's paper was published, mathematicians and computer scientists worldwide have been racking their brains as to whether the Bonn-based researcher has, in fact, solved this Millennium Prize Problem. After an initially positive reaction, such as the one from Stanford mathematician Reza Zadeh, doubts are beginning to arise about whether Blum's reasoning is correct. In a forum for theoretical mathematics, a user named Mikhail reached out to Alexander Razborov -- the author of the paper on which Blum's proof is based -- to ask him about Blum's paper. Razborov purports to have discovered an error in Blum's paper: Blum's main argument contradicts one of Razborov's key assumptions. And mathematician Scott Aaronson, who is something of an authority in the math community when it comes to P vs. NP, said he would be willing to bet $200,000 that Blum's mathematical proof won't endure. "Please stop asking," Aaronson writes. If the proof hasn't been refuted, "you can come back and tell me I was a closed-minded fool." In the week since Aaronson's initial blog post, other mathematicians have begun trying to poke holes in Blum's proof. Dick Lipton, a computer science professor at Georgia Tech, wrote in a blog post that Blum's proof "passes many filters of seriousness," but suggested there may be some problems with it. A commenter on that blog post, known only as "vloodin," noted that there was a "single error on a subtle point" in the proof; other mathematicians have since chimed in and confirmed vloodin's initial analysis, and so the emerging consensus among many mathematicians is that a solve for P vs. NP remains elusive.

A German man -- Norbert Blum -- who claimed that P is not equal to NP is seeing several challenges to his solution. From a report: Numerous mathematicians have begun to raise questions about whether the German mathematician solved it at all. Since Blum's paper was published, mathematicians and computer scientists worldwide have been racking their brains as to whether the Bonn-based researcher has, in fact, solved this Millennium Prize Problem. After an initially positive reaction, such as the one from Stanford mathematician Reza Zadeh, doubts are beginning to arise about whether Blum's reasoning is correct. In a forum for theoretical mathematics, a user named Mikhail reached out to Alexander Razborov -- the author of the paper on which Blum's proof is based -- to ask him about Blum's paper. Razborov purports to have discovered an error in Blum's paper: Blum's main argument contradicts one of Razborov's key assumptions. And mathematician Scott Aaronson, who is something of an authority in the math community when it comes to P vs. NP, said he would be willing to bet $200,000 that Blum's mathematical proof won't endure. "Please stop asking," Aaronson writes. If the proof hasn't been refuted, "you can come back and tell me I was a closed-minded fool." In the week since Aaronson's initial blog post, other mathematicians have begun trying to poke holes in Blum's proof. Dick Lipton, a computer science professor at Georgia Tech, wrote in a blog post that Blum's proof "passes many filters of seriousness," but suggested there may be some problems with it. A commenter on that blog post, known only as "vloodin," noted that there was a "single error on a subtle point" in the proof; other mathematicians have since chimed in and confirmed vloodin's initial analysis, and so the emerging consensus among many mathematicians is that a solve for P vs. NP remains elusive.

JoshuaZ writes: A major open problem in graph theory is how efficiently one can tell, given two graphs, whether or not they are isomorphic — that is, whether they're the same graph with just the labels changed. This problem is famous, along with factoring integers, as a problem that is potentially in between P and NP in difficulty. Now, Laszlo Babai has reported that he has a quasipolynomial time algorithm which he sketched out at a set of talks at the University of Chicago. Scott Aaronson was one of the first to break the news, and his latest blog entry and its comments contain further discussion of the result. The new algorithm places the problem of graph isomorphism as, at most, just barely above P. Babai's result depends on the classification of finite simple groups, a deep result in algebra whose proof consists of thousands of pages over hundreds of distinct papers. Unlike the problem of factoring integers, improvements in this algorithm are unlikely to impact cryptography in any direct way, since no cryptographic systems depend on the difficulty of determining when groups are isomorphic.

gbrumfiel writes "Last week, Google and NASA announced a partnership to buy a new quantum computer from Canadian firm D-Wave Systems. But NPR news reports that many scientists are still questioning whether new machine really is quantum. Long-time critic and computer scientist Scott Aaronson has a long post detailing the current state of affairs. At issue is whether the 512 quantum bits at the processor's core are 'entangled' together. Measuring that entanglement directly destroys it, so D-Wave has had a hard time convincing skeptics. As with all things quantum mechanical, the devil is in the details. Still it may not matter: D-Wave's machine appears to be far faster at solving certain kinds of problems (PDF), regardless of how it works."

the_newsbeagle writes "This article discusses a proposal to create cash that can't be counterfeited by embedding quantum particles in banknotes. A counterfeiter trying to copy a real bill would have to precisely measure all the attributes of the embedded quantum particles — which is impossible under the tricky laws of quantum mechanics (PDF). MIT computer scientist Scott Aaronson, who famously offered a prize for anyone who could prove quantum computers are impossible, said, 'This is science fiction, but it’s science fiction that doesn’t violate any of the known laws of physics.'"

mikejuk writes "Quantum computing is currently a major area of research — but is this all a waste of effort? Now Scott Aaronson, a well-known MIT computer scientist, has offered a prize of $100,000 for any proof that quantum computers are impossible: 'I'm now offering a US$100,000 award for a demonstration, convincing to me, that scalable quantum computing is impossible in the physical world.' Notice the two important conditions — 'physical world' and 'scalable.' The proof doesn't have to rule out tiny 'toy' quantum computers, only those that could do any useful work."

jamie writes "As some of you may have heard, the incoming Republican majority in Congress has a new initiative called YouCut, which lets ordinary Americans like me propose government programs for termination. So imagine how excited I was to learn that YouCut's first target — yes, its first target — was that notoriously bloated white elephant, the National Science Foundation."

Scott Aaronson recently had "A Mathematician's Lament" [PDF], Paul Lockhardt's indictment of K-12 math education in the US, pointed out to him and takes some time to examine the finer points. "Lockhardt says pretty much everything I've wanted to say about this subject since the age of twelve, and does so with the thunderous rage of an Old Testament prophet. If you like math, and more so if you think you don't like math, I implore you to read his essay with every atom of my being. Which is not to say I don't have a few quibbles [...] In the end, Lockhardt's lament is subversive, angry, and radical ... but if you know anything about math and anything about K-12 'education' (at least in the United States), I defy you to read and find a single sentence that isn't permeated, suffused, soaked, and encrusted with truth."

Pickens writes "MIT computer scientist Scott Aaronson has an interesting post on how to improve Wikipedia's coverage of theoretical computer science. Aaronson writes what while Wikpedia will never be an ideal venue for academics because 'we're used to (1) putting our names on our stuff, (2) editorializing pretty freely, (3) using "original research" as a compliment and not an accusation, and (4) not having our prose rewritten or deleted by people calling themselves Duduyat, Raul654, and Prokonsul Piotrus,' he identifies twenty basic research areas and terms in theoretical computer science that are not defined on Wikipedia, and invites readers to write some articles about them. Article suggestions include property testing, algorithmic game theory, derandomization, sketching algorithms, propositional proof complexity, arithmetic circuit complexity, discrete harmonic analysis, streaming algorithms, and hardness of approximation. One commenter suggests that professors should encourage students to improve the Wikipedia articles about topics they are studying. 'This will help them understand the topic and at the same time improve Wikipedia.'"

Scott Aaronson offers an intriguing call for ideas on how nerds can supercharge the political process this year. He's clearly an Obama admirer and phrases his challenge this way: "What non-obvious things can nerds who are so inclined do to help the Democrats win in November?" But the question itself is not inherently partisan. The analogy Aaronson gives is to the Nadertrading idea in 2000 (which we discussed at the time). What's the Nadertrading for 2008? "The sorts of ideas I'm looking for are ones that (1) exploit nerds' nerdiness, (2) go outside the normal channels of influence, (3) increase nerds' effective voting power by several orders of magnitude, (4) are legal, (5) target critical swing states, and (6) can be done as a hobby."

The Narrative Fallacy writes "Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (PDF) discussing the question: Will quantum computers let us transcend the human condition and become as powerful as gods, or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine? Aaronson says that while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there's reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics and that this may be a fundamental limitation on technology no different than the second law of thermodynamics or the impossibility of faster-than-light communication."

MIT EECS Assistant Professor Scott Aaronson was just notified that Australian actresses are plagiarizing his quantum mechanics lecture to sell printers. The world is a very odd place.

Update: since his site's down temporarily, here's some quantum physics to tide you over.