The issues center around a group of classic computer science problems, like the traveling salesman problem — how to figure out the most efficient route through a number of cities given certain constraints. Factoring a large number is also a good example of what is referred to as an NP problem. At present, there is no understood method for doing it in polynomial time, but given an answer it is easy to check to see if it is correct…Checking to see if any particular solution is correct is simple, but finding the best solution in the case of very large problems is infinitely difficult.
Good to see some press for this great problem and theoretical computer science in general. And getting a mention in the Times impresses my mom more than any JACM article ever could.
One of the sentences is tricky to parse.
An esoteric branch of mathematics known as algebraic geometry may offer an avenue to prove or disprove the problem, which was first outlined by Stephen A. Cook, a University of Toronto computer scientist, in 1971.As you readers should know, while Cook (and independently Leonid Levin in Russia) first outlined the P vs. NP problem, the much more recent algebraic geometry approach is primarily due to my former U. Chicago colleague Ketan Mulmuley.