https://en.m.wikipedia.org/wik...â"Levin_theorem Cook showed that any decision problem with easily checkable solution could be mechanically and quickly converted into a Boolean satisfiability problem of similar size. Thus, SAT became the first known example of a so called NP-complete problem. Other examples are then much more easily found by giving a procedure to convert SAT problems into that kind of problem. Such a procedure was apparently given for some variation of the queen problem. So in fact yes, an algorithm fast for specifically queens can be composed with the (already known) fast transformation from SAT and ultimately through Cooks construction for any particular NP problem (where he is able to be completely general by taking as input the Turing machine for the solution checker)

If you think it's unbelievable, that's completely natural. No one would suspect the existance of NP complete problems from the start.

First of all, the problem cant in any real sense be considered a chess puzzle, except in the superficial sense of placing queens on a board. Chess reasoning has nothing to do with a solution of the problem.

Second of all, the $1m prize is exactly the clay millennium prize for the resolution of P vs NP. If n-qeens has a solution in P, being NP-complete, this implies P=NP.

tldr Sensationalist title is sensationalist

The solution to *any* problem that has resisted solution for as long as this has will likely contain essentially new ideas. These new methods of analysis likely have a much broader application than strictly the original problem. Many minds following the threads through and having their own insights will result in an improvement in the state of the art which you would find in even the most practically minded engineers textbook.

Personally, I think knowing the why to the answer to the question "can a problem whose solution is easily checked actually be hard?", whatever it is, is interesting enough in its own right.

Do you have a reason to distrust all of our intelligence services?

Aside from eliminating privacy for everyone, can measures like this be expected to actually fight terror or crime at all? Encryption is essentially a solved problem; a coordinated terror group needs only do a little work to make its own app using strong end to end encryption in the backend. Insisting that popular messaging apps be insecure simply robs the common citizen from privacy protection tools without addressing the problem which is claimed to be tackled.

In latex, to force word spacing after an abbreviation, you escape the space like '\ '. I suppose if it has to be spaced as a text document, the editor should unconditionally insert two spaces after a period, then in the case of an abreviation the user should backspace.

What one sees as the "concept of free speech" is obviously dependent on your definition. If you are speaking of the free speech legislated in the first ammendment, it only protects the people from government, not from private individuals. In fact the only constitutional provision which limits the actions of private individuals is the 14th ammendment, which outlaws slavery.

Now there could in principal be federal or local laws which somehow protect free speech from infringement by other private individuals, but I'm not aware of an example, and indeed this is usually not the case (nor should it be in my opinion).

Arctic ice affects Y by the albedo effect.

It sucks because warming removes arctic ice, which no longer reflects sunlight, which causes more warming. The summary suggests that when (in the future) arctic ice goes away completely during the summer, this will be very bad.

Ones that even beat the proprietary competitors too, see http://tests.stockfishchess.or.... This is not to mention efforts like folding@home and similar. Of course there is still the problem of having large training data sets.

Hmm, theoretically impossible? I guess, *in principle*, any user could always just reformat and install Windows XP, but granting that at least *some* system components can be trusted, there is the notion of http://en.wikipedia.org/wiki/Proof-carrying_code/ which, although not commonly implemented due to the technology not being there yet for widespread adoption, could conceivably be implemented as a system wide policy.

The idea is that each piece of code contains within it a proof of its compliance with some formally specified security policy defined by the system, which the system verifies before the code is allowed to execute. The result is, as long as you can trust the security policy and things like the program loader, you can trust everything that executes, regardless of origin.

While writing this, it occurs to me that maybe the issue with even this system is no security policy could simultaneously allow all nonmalicious software features while excluding all malicious features, even in principle. A proof of this isnt so obvious to me though

To be pedantic, we still cant conclude the product + 1 is prime, only that it is a contradiction that it is divisible by no prime (which is all we need anyway). The GP is correct in that a proof more similar to Euclid's original is given by considering an arbitrary finite set P of primes, letting N be the product of the P plus 1, and then concluding that a prime divisor of N must not be in P.

It is important to remember that while a naive approach to functional programming (that is, using the same data structures and idioms as for imperative languages), will indeed be inefficient due to enforced persistence, much of the loss can be mitigated by using better data structures. For instance, Data.Sequence of Haskell supports access and modification time logrithmic in the closest distance to one end of the sequence, and does so in a thread safe (as always) way.

Even in the case where we demand mutable data structures because nothing else is acceptable, we can control the access in a purely functional way using monads (a very cool concept which arent as scary as they first might seem). See for instance, the haskell State monad and mutable data structures.

he postulated tachyons and their properties again?

A judge who dismisses a case on grounds of 'public interest' and not rule of law is overstepping his authority. As broken as our patent system is, much worse is a judiciary which disregards the checks and balances established for it by our Constitution. Perhaps Apple and Motorola are being childish, but they are acting in a manner they believe benefits their stockholders the most within the confines of the law, which is the extent of the court's authority.

Granted, I havn't read the case materials, and the judge may have a more legitimate legal basis to cancel the jury trial.

Well the lowest risk investment you can make these days is in a US Treasury Bond, essentially investing in US debt. One could argue that if the government is trying to create jobs by spending money, giving the government money will lead to job creation. Of course, this depends both on the government being successful at job creation by spending money, and that rich people would actually invest in treasury bonds. The interest rate on treasury bonds is so low right now its actually risky to buy because if the interest rate then increases, the price of the bond you own drops signifigantly (http://en.wikipedia.org/wiki/Interest_rate_risk).

Much more likely for large investments is diversified stocks, possibly managed inside a mutual fund. Diversification mitigates risk of temporal losses of investment value, but the stock market has a much higher historical (average) rate of return than bonds. Stocks give money to companies to spend on their business, which more directly contribute to job creation.

Even if you let your money collect dust in a low-risk savings account in a bank somewhere, the bank's business is to reinvest your money in the above. There are also other investment opportunities, but they all involve your money ultimately getting to companies or the government (but to be fair only mostly US companies and governments).