Slashdot Mirror

The new research concerns the n-Queens Completion Problem, where not only is the board larger, but also some queens have already been placed. That is, if some queens have already been placed on the n-by-n board, can you find a solution to the n-Queens puzzle without moving any of those queens?

...

First, as just mentioned, the paper is about the n-Queens Completion problem, not the original n-Queens puzzle. Second, even the discovery of an algorithmic solution to the n-Queens Completion puzzle for all n would not be enough. What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”

anything larger that 8x8 isn't a chess board - problem solved, where's my money?

Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board, etc. board. Move it over, put it in the same relative location in the 8x8 group at the corner of the larger board, done. So solve for 8x8 and move.

So you'll need to split that money with me, pal. :)

Of course, it's just slightly possible that TFS is not an accurate summary of the actual article / problem, but...

Nah. Besides, everyone knows that reading TFA is un-American. Even reading the summary raises red flags with Homeland Security, and may result in a National Security Letter (which you can read, but can't discuss.)

You are correct, the article and the summary are misleading/wrong.
Here's those guys explaining the problem and prize again.
https://www.claymath.org/event...

Well said. Btw, you used the word "engineer" when it should have been "programmer". Developing software is not a physics-based discipline like electrical, mechanical or chemical engineering and therefore is nowhere near the rigor required to be "engineering".

Go try to solve Primes in P and let me know how much easier it is than electrical, mechanical and chemical engineering. By the way, you might also get a million dollars if you can because it might help solve P vs NP. But you know, mathematics is easy right especially for you electrical engineers. Easy peasy. Godspeed my friend! p.s.: I find it funny this debate has been raging for decades. :)

I'd counter that long term R&D simply isn't something most companies these days can budget for. That's not because the government is competing with them, it's because the stock market demands that they produce higher quarterly profits every single period.

Well, ever wonder why the stock market demands that? If one looks at older times, before the Second World War and the Great Depression, there was the same greed and same short sightedness. But somehow companies figured out how to invest for the future. Well, not everyone obviously, but enough. What changed?

My view is that it is a systemic set of incentives from implicit bailout guarantees for large scale failure, regulation that rewards caution over risk taking, and of course, vast amounts of uncritical government funding for research without the messy details of actually needing to produce anything of value. It is these things which results in a business environment that has little need to think past the next quarter.

If you want businesses to engage in long term thing, then you need to change the incentives. I don't know, maybe you like businesses that can't do long term. But that doesn't sound like what you really want.

And thus, that leads us to this moderately counterintuitive point. If you want to increase the research done by your country, then you need to delegate that research to the private sector rather than publicly fund it directly. And if one wants a constructive way for public funds to spur research, consider prizes. For example, the Clay Millennial Prize Problems in mathematics show a way one can encourage productive research even in abstract fields.

But to just do more of the same thing that is causing the problem in the first place? That needs a rethinking.

You're using the Skunkworks as an example? Seriously? Hint: The Skunkworks built airplanes for the US government, under US government contracts. Here's the list of planes they built- see anything civilian on that list? A number of your other examples are dubious at best- a huge amount of GE's R&D is government funded through the military. Bell Labs existed only because Bell had a monopoly on phone service- it's no accident that as soon as that monopoly was gone and they had to compete in a free market Bell Labs was gone as well.

I see no dubiousness in any of those examples. The part about funded through government (military or whatever) indicates another avenue by which public funding corrupts scientific progress. These companies are paid to do research. They aren't paid by result. I believe that little fact adds a zero or two to the cost of everything they do for the government.

Physics is math.
Chemistry is physics.
Mechanical engineering is physics.

What does that leave as patentable? Marketing?

The reason for a patent to exist is for an original inventor to gain profit from a novel solution to a problem. Suppose someone had an algorithm to efficiently solve the general case of the Navier-Stokes equations. The impact would be immense for aerospace and engineering. If you don't want to patent it, a $1,000,000 prize is up for grabs.

I'm as skeptical as the next guy of Quantum Computing mumbo jumbo, but I actually okay with the idea that the QC may not know what it's solving. Here's why:

From the P vs NP official problem description:

Of central importance in computability theory is the notion of reducibility, which Turing defined roughly as follows: A language L1 is Turing reducible
to a language L2 iff there is an oracle Turing machine M which accepts L1, where M is allowed to make membership queries of the form x \isin L2 ? which
are correctly answered by an “oracle” for L2 .

The oracle doesn't know anything about L1; it only understands L2. However, M can still use the oracle to solve its problem by encoding L1 as an instance of L2.

My position is that it's highly plausible that QC's have the same type of reduction property.

it is hard to get past the "How do you program games?" point.

Well then, send them off the deep end. Show them a simulation in a game that uses fluid dynamics (i.e. smoke)... then show them the math. Job security for the rest of us :D In case you find a real geek, tell them that if they find a smooth solution for this that they win $1 million.

It's also worth a cool $1 million if you solve it, thanks to the Clay Mathematics Institute, because it's currently one of the top unsolved problems in all of mathematics as well as being the top unsolved problem in the more specialized computer science world.

And to give you an example of how awesome it would be if P=NP: You could (in theory at least) write a program that took a set of axioms and a hypothesis, and it could tell you reasonably quickly whether the hypothesis was something that could be proven using those set of axioms. Or for architecture and engineering, right now there are programs that can do a lot of the checking of whether a bridge design would collapse, but with this sort of program you could write something that says "design me a bridge that can take a 15-ton load". In short, it would revolutionize what sort of problems computers could solve for us.

However, I should point out that unlike a date, the computer scientists might actually succeed at figuring this one out.

and other games...

If "non-deterministic polynomial time" is an actual "algorithmic complexity class' [...]

Was that tongue-in-cheek? Those terms are pretty standard for the topic, at least in American English. Either you don't know much about complexity theory, they used different terms in the language/region/era you learned about it and you weren't able to see the connection to these phrases, or that was a superb troll. Here's a link to the Millennium Prize description of the problem (pdf link). The first sentence of that document (emphasis mine) is:

The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.

Replying to my own comment.

The minesweeper consistency problem is actually NP-complete. That problem consists of trying to find a mine-solution to the numbers on a grid.
http://www.claymath.org/Popular_Lectures/Minesweeper/

A simple description is that there are problems where you can quickly figure out that a given solution is correct, but where it takes a very long time to actually find a solution. There's a nice description here: http://www.claymath.org/millennium/P_vs_NP/

NP-class problems can be translated into minesweeper puzzles. The problem is determining whether a solution exists in polynomial time. Your example is not solvable. The problem is determining whether a solution can be determined for arbitrarily large puzzles in a polynomial-scale algorithm, or whether the amount of time needed basically grows exponentially. This guy is saying that it grows basically exponentially.

See here for a more complete explanation: http://www.claymath.org/Popular_Lectures/Minesweeper/

These guys must be crazy. Why waste your career proving the regularity of solutions to the Boltzmann equation when you could get a million bucks for doing the same for the Navier-Stokes equations.

What Millennium are we talking about here? Its now 2010, 9 years after the start of the new Millennium.

Just in case that wasn't a joke:

http://www.claymath.org/millennium/

The challenge was set in 2000

The phrase "Well Duh!" comes to mind. I'm mean seriously is this research or just some people sitting around a table in a bar after 10 pints drunkly going

The social sciences, of which economics is a part, must do research and gather evidence to back up their conclusions; even those which should be obvious to everyone. This is really not so different from proofs in other fields where even 'obvious' statements must still be proven or at least investigated. For example everyone 'knew' that Fermat's Last Theorem was true or at least the evidence strongly suggested that a counter example would not be found. However, it still had to be "proven", no matter how obvious, and that took 358 years from the time that Fermat proposed it. There is another example in the field of computer science where everyone 'knows' that P != NP, but as of yet nobody has been able to prove that (btw: the proof is worth $1 million from the Clay Mathematics Institute...its one of the Millenium Prize Problems).

Caveat: I am not an expert on BSD, but my advisor is.

First place to look is here: http://www.claymath.org/millennium/Birch_and_Swinnerton-Dyer_Conjecture/. For one thing, the BSD conjecture implies that the title of this story is accurate. But, we don't even know that. Consider Fermat's last "theorem" -- the linchpin was a theorem "All Elliptic Curves are Modular" -- before that, we knew that modular elliptic curves behaved quite nicely, but we didn't know if there were other elliptic curves. To this day, we can prove remarkably little about very obvious-looking trends that we see in data about elliptic curves. Assuming BSD, many computations about elliptic curves are suddenly tractable.

Ok, but what does this have to do with the country's bottom line? Directly, I'd say "nothing". Indirectly, though, this is providing a lot of interest to American mathematicians. The current thinking is (hah) a bit of a trickle-down effect. As undergrads study, they gravitate towards the more interesting fields -- if math looks sexy, we get more mathematicians. The more mathematicians graduate, the more funding mathematics departments will get in a very direct way -- this gives us better teaching budgets, which should effect an increase in the number of good math teachers. The more good math teachers we have, the better our students will learn. That's the hope, anyway.

up to U.S. $7 million if I solve all of the Millenium problems.

Yours In Valium,
Kilgore Trout

one MEEEEEEEEEELION dollars
http://www.claymath.org/millennium/Riemann_Hypothesis/

Peer review is the single most important aspect of scientific/mathematical development, and that doesn't exist online, unless it's reprinting the peer reviewed journals. The process for journal publication is what ensures that there is quality being printed and that multiple other scientists agree with the results (or rather, don't find problems with it).

You'll notice http://www.claymath.org/millennium/ has seven, $1million problems and the money won't be awarded until a solution has been published, and survives the peer review process for two years. Without this process, there is no mechanism for separating people who sound like they know what they're talking about, and people who *actually* know what they're talking about.

Well the Clay Mathematics Institute is currently offering seven figure sums for seven different math problems. I can't say that much of a dent has been made on most of those problems. In fact the only solved problem had the solver (Perelman) turn down the cash. Perhaps $1 million isn't enough -- compared to the prize for solving the longitude problem, adjusted for inflation, it's pretty small. Perhaps we should be talking about 8 figure sums? If we can pay an actor $20 million dollars to appear in a film, is it really that bad to pay a researcher (or team of researchers) $20 million for solving the Hodge conjecture, or proving P!=NP?

Well the Clay Mathematics Institute is currently offering seven figure sums for seven different math problems. I can't say that much of a dent has been made on most of those problems. In fact the only solved problem had the solver (Perelman) turn down the cash. Perhaps $1 million isn't enough -- compared to the prize for solving the longitude problem, adjusted for inflation, it's pretty small. Perhaps we should be talking about 8 figure sums? If we can pay an actor $20 million dollars to appear in a film, is it really that bad to pay a researcher (or team of researchers) $20 million for solving the Hodge conjecture, or proving P!=NP?

There's a $1 million prize for proving or disproving P = NP from the Clay Mathematics institute if you're still interested.

A math position at a university?

I mean, even being in grad school gets you a decent stipend and a fee waiver - and a post-doc usually pays enough (in fact, when I was at a certain national labs, physics post-docs were earning 75-100k).

And if you are a research scientist, you earn more. If you become an assistant professor? Even more, not to mention other perks. Associate professor? Tenured? It goes up, up and up - and you get to do other things than just teach (e.g. partnerships with the industry) etc.

So, why bother teaching school kids when you have that path open in front of you?

And btw, there is no one "Riemann-theorem" -- there are several Riemann theorems. Perhaps you mean the Riemann zeta hypothesis that talks about the distribution of zeroes of the Riemann zeta-function?

I doubt it, that would mean a TSP solution in polynomial time. Did anyone tell you that TSP path must loop ? You must come back to your starting point.

Anyway, you should be able to work it out again. If you are correct, publish it and you have won at least a million dollar proving P=NP.

Undying fame awaits you. Or you might just be wrong, I don't know.

In order to celebrate mathematics in the new millennium, The Clay Mathematics Institute of Cambridge, Massachusetts (CMI) has named seven Prize Problems. The Scientific Advisory Board of CMI selected these problems, focusing on important classic questions that have resisted solution over the years. The Board of Directors of CMI designated a $7 million prize fund for the solution to these problems, with $1 million allocated to each. During the Millennium Meeting held on May 24, 2000 at the Collège de France, Timothy Gowers presented a lecture entitled The Importance of Mathematics, aimed for the general public, while John Tate and Michael Atiyah spoke on the problems. The CMI invited specialists to formulate each problem.

link

In a world where some of the best scientific minds can (typically) make more money producing drug which will give you a nice tanned look than solving complicated mathematics problems (or disproving the man-made global warming hypothesis) sometimes you need a greater incentive than "it's the right thing to do".

The truth is that if you attempt to find evidence that man made global warming isn't happening you're going to end up causing yourself endless problems in academic, political and social circles and many people are not going to try because the cost is to large. Any evidence you find will rapidly be used by groups to disprove global warming, every environmental group will attempt to discredit you, and you will likely be mentioned in countless political debates.

How about the Nobel and the Fields? But if you want some quick cash try one of these: http://www.claymath.org/millennium/
---
http://mdsolar.blogspot.com/2007/01/slashdot-users -selling-solar.html

• Millenium Math Problems
• International Campaign to Ban Land Mines
• World Peace
• Where are my socks?
• Where's Waldo?

I've read all the posts up to now, and most are overlooking what I think is an important fact.

The Clay Institute has put up a bounty of one million US dollars for a proof of this conjecture.

There seems to be a good chance that Perelman will decline it (or his share of it), given his behavior.

This may be a factor in Yau's rush to get a share of the credit. He's famous enough that he doesn't really need to do this to improve reputation.

harder than quantum mechanics

Armed with a basic knowledge of quantum mechanics you can start solving problems using little more than basic linear algebra or the theory of partial differential equations. You can start computing energy levels for simple atoms, or estimate tunneling probabilities, or derive some qualitative features of the conduction of current through crystalline materials.

Turbulent flow, on the other hand, is incredibly difficult. The usual mathematical tools (such as the theory of partial differential equations mentioned above) fail in all sorts of ways. The dynamics are nonlinear and highly sensitive to initial conditions. It's hard to derive statistical properties of the chaotic regions of the dynamics. We often have to fall back on empirically derived rules. Even in a perfect fluid that exactly satisfies the Navier-Stokes equations it is hard to make long term predictions - which is why one of the Millennium Prize problems is about these equations.

Harder than quantum mechanics? That really isn't saying much.

The basic equations of fluid mechanics, the Navier-Stokes equations, are a second order, non-linear system of partial differential equations.

Other programming challenges -- with useful results are sitting around all over the place that just need some more money to get the competition kickstarted.

Proposing prizes as the motivation for scientists shows that you do not understand how scientific work gets done.

Of course, there are prizes around, offered to people that solve specific unsolved problems (like, say, the Clay Milennium Prize Problems), and, more usually, prizes given out to people for their achievements.

But relevant scientific work is not only the solution of those "prize-worthy" problems like the ones you list, but the every day toil in the quest for information, without which those big problems would never ever be solved. If for some reason we were left only with the geniuses, science would essentially stop.

Rewarding geniality only is blindness, as science is not built upon the work of geniuses. Geniuses do show the way, but the roads are not usually built by them. And, do note, it is quite rare that society can benefit from the mere knowing of where the way is: society needs to get to where the way leads to.

Q. which is better: vi or emacs ?. I want to KNOW,
with conclusive and definative proofs. Oh and, err
Q. Is every language accepted by some nondeterministic algorithm in polynomial time also accepted by some deterministic algorithm in polynomial time ?
sorry, thats two important questions, isn't it

There is no problem that the Slashdot community can't solve. So what about that tiny 'P versus NP' problem?

1.Find problem on Slashdot
2.Solve problem
3.Email to generous stranger
4.Get $10 via PayPal
5.Profit!
See how easy that is! No tricks here...

* - by accepting the $10, you transfer all claims to any further monetary compensation from any party to Comatose51, including but not limited to $10 million from the Clay Institute

Minesweeper is NP-Complete, which is basically a haughty way of saying "it's probably very difficult, but if you can prove whether it is or not, there's a million bucks in it for you"

[another interesting link on the subject]

Minesweeper is NP-Complete, which is basically a haughty way of saying "it's probably very difficult, but if you can prove whether it is or not, there's a million bucks in it for you"

[another interesting link on the subject]

you can get rich by solving famous mathematical problems:

http://www.claymath.org/millennium/

I'm sure there are other prices for cracking crypto-problems and/or factoring large integers.

Professor Richard Hamming was fond of saying that you can get money beyond your dreams if you solve any one of the 3 hardest problems in physics - timetravel, antigravity, or teleportation. Do you see Physics majors attacking these problems tooth & nail ? As Hammings explains, there's just no known attack.

Americans aren't warming up to the sciences simply because they have a choice. Students get to decide what they want to study. They look at the difficulty levels of the subject, the job market, ask their peers & parents, look at career prospects & evaluate their "sexiness", and decide to major in English & Communication & Marketing instead. In India, where I come from, you simply didn't have a choice, (well, not until you were 18 anyway, by which time it was too late for most of us). You were asked to digest megadoses of math & science in high school. Hell, I remember working on some "preliminary math" problems when I did my Masters in CompSci in the US. The problems were ones I had previously encountered when I was in my early teens, in my high school! But the Professor said American undergrads needed that sort of thing!!

You guys have a choice, so you study literature & photography & journalism & whatnot in your high school. In India, the only choices are math, more math & much more math. So I can comfortably handle a second order differential equation. But to this day I have not studied Shakespear ( spelling ? ), Rosseu, Homer ( not simpson, the pgilosopher chap), Keats, Byron or any other literary figures. I just know the names cause we crammed them for various "general knowledge" quizzes!

Education systems are broken all over the world. In places like India & China, we get a one-sided hard-core math-sci curricula with no literature. In the US/UK, you guys get liberal arts with less math/science than what Bill Gates wants to hire.

Prizes are not the answer (Nor is a $100 laptpop for developing nations). I don't know what is.

I remember in HS we once watched a play on DVD on Fermat's Last Theorem. It was called Fermat's Last Tango . It was a rather interesting thing seeing mathematics portrayed in a musical form, and to this day, I still recall parts of the lyrics.....

This is the real problem beyond Fermat

Before this you should prove that there is a mass gap in Yang-Mills theory: http://www.claymath.org/millennium/Yang-Mills_Theo ry/ (and in the process earn a million dollars)

Maybe, maybe not. Either way, you get a million bucks if you figure out which one it is.

Quantum computation is a whole other matter. Complexity Theory sorts problems into classes such as the famous P and NP classes ($1 million to anyone who can prove P=NP or P!=NP). Determining whether a number is prime is in P. Factoring a number is in NP. Actually, factoring is in QP, the set of problems solvable in polynomial time by a quantum computer. P is a subset of QP is a subset of NP. Whether QP=NP is not known. Whether it is possible to make a big enough quantum computer is not known. (I entertain the thought that quantum computers might have the same problem as warp drive-- they would work except that they take far more power than it will ever be possible to supply.)

Since NP might be bigger than QP (which would mean P!=NP), there may be problems that can still be used for public key encryption even if a big enough functional quantum computer can be made. The only ones I know of are the factorization problem for RSA encryption, and the discrete logarithm problem for the older Diffie Hellman method. Both are in QP. Each of the attempts to make public key encryption from some other NP problem such as bin packing, 3-sat, or traveling salesman, has so far turned out to have some flaw.

Would be a real shame not to have any way to do public key encryption. Quantum computation breaks RSA and DH. No one knows whether it breaks the idea of public key encryption, However that turns out, the old symmetric key methods will still be safe. So yeah, the possibilities are exciting, just not quite what people think.

CSS is/was an enclosed system, did not involve a negotiation between peers [i.e. did not involve the potential for an exchange of public keys and the withholding of private keys], and, region-coding aside, did not involve session-based [i.e. individualized] encryption. Therefore it was theoretically breakable [all you had to do was place the de-encrypting software in a "de-bugger" and spend thousands - or maybe millions - of man-hours going over shift register logic to figure out what it was they were doing for the "encryption"].

The cable services are moving towards a really onerous model, however [onerous from the point of would-be pirates]:

1) Cable is rapidly moving away from a broadcast-based network infrastructure [where you can put a "sniffer" on the network and "hear" everyone else's traffic], and towards an on-demand switched network [where you can only hear the traffic that is streamed directly to your jack], so that you can't even sniff the network to begin with [unless you were to physically break into your neighborhood's cable switch, and that sort of thing just screams local/state/federal "FELONY OFFENSE"].

2) Even if you could sniff the network, the new smart boxes and smart protocols are doing public key exchange [in combination with private key withholding], so, unless you solve a Clay-Prize-worthy problem in mathematics, you're SOL as far as understanding what it is you're sniffing [which I guess is the point that the parent comment was making].

PS: I once downloaded one of the new cable protocols - I think it was a story on /. at the time - and, while I can't seem to find it at the moment, I quite clearly remember that there was some seriously tedious, non-trivial communications theory that went into it - enough to make e.g. something like the Token Ring protocol look like a day at the beach by comparison. And if you ever saw one of Laura Chappell's old books with the fold-out diagram of the Token Ring packet, you'll know I ain't talkin' turkey here.

You must have a proof that P!=NP if you can say impossible. Claim your prize It has been shown that unless we have P=NP => no pseudo-randomness => one-way hash functions do not exist, then it will indeed be possible.

There's a lot of incomprehension in the comments about higher mathematics. The fact that all four of the Clay Mathematics Institute Research Fellows this year are not native Americans indicates the truth of the AeA's comment on math teaching in American schools. I note that all of the fellows are in topology or closely related areas. My doctorate is in combinatorics, "the slums of topology", so I'm probably not qualified to explain the Atiyah-Singer theorem to y'all!