P is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.
Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work now—a task that could go on for a long time. If he’s correct, Deolalikar will have figured out one of the Clay Mathematics Institute’s seven , for which they give $1 million prizes. (Grigory Perelman won one of the seven for solving , but last month.)
What’s all the hubbub? First, an explainer:
The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P. If the answer to a task can be checked quickly then it is in class NP [].
That definition is pretty abstract, so here’s a more concrete example:
Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large — more than the total number of atoms in the universe — but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean’s prohibited pairs is on the list, that’s an error [].
Thus, if P were equal to NP, it would mean that problems that are easy to check—like this roommate match-up—must also be easy to solve. But if Deolalikar is correct and in fact P is not equal to NP, , then that ain’t necessarily so. And that would have practical meaning, according to Michael Sipser of MIT.
Sipser … says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says [].
Deolalikar’s proof is now . and report that he pulled together tactics from different disciplines to show that an NP problem—whether a list of statements can be simultaneously correct or contradict one another—is not a P problem, because it can be easily checked but no computer can figure it out quickly from scratch.
In the days since the proof began to spread across the Internet, however, some math bloggers like have responded to the proof by saying yes, it’s lovely, but no, it probably isn’t going to stand.
Yesterday, Google and Verizon posted their joint for internet regulation. The proposal suggests a for Congress regarding our current “open internet.” An open internet means all bits are treated the same: internet service providers process every internetcontent provider’s information at the same speed–YouTube or Hulu, Wikipedia or Britannica. Though the Google Verizon plan is titled “a joint policy proposal for an open Internet,” it leaves some internet neutrality champions concerned; the plan does not address wireless service regulation and allows exceptions to the open internet standard for special broadband services.
We’ll break down the possible implications of this move, but first, a briefing on the basics.
What is an example of an alternative to our open internet? Internet content providers could pay more to get their information to you more quickly–like paying for a plane ticket instead of taking the bus. Since October of 2009, Verizon and Google have issued a shared , submitted a to the FCC, and published a on net neutrality. But after talks between the two companies, a New York Times and others asked if Google–a self-proclaimed proponent of net neutrality–might pay Verizon to get information to users more quickly, thus ending our net neutral system.
In April, a federal appeals court that the FCC–which can regulate interstate and international communications by radio, television, wire, satellite and cable–cannot regulate the way internet service providers conduct business. So instead the FCC, which has said it’s in favor of the current open internet, invited major internet players to a series of meetings to devise an agreement. But after weeks of private meetings, talks seem to be breaking down:
The F.C.C. in recent weeks has been trying to negotiate its own agreement in a series of private meetings with a group of big Internet service and content companies, including Google and Verizon, to ensure net neutrality. But the agency canceled a session scheduled for Thursday after the reports of the Google-Verizon talks. [An FCC spokesman] said in a statement that the effort “has been productive on several fronts, but has not generated a robust framework to preserve the openness and freedom of the Internet, one that drives innovation, investment, free speech and consumer choice.” []
The joint statement published yesterday says that Google and Verizon’s plan is meant to achieve two main goals:
1. Users should choose what content, applications, or devices they use, since openness has been central to the explosive innovation that has made the Internet a transformative medium.
2. America must continue to encourage both investment and innovation to support the underlying broadband infrastructure; it is imperative for our global competitiveness. []
The whole issue has brought out varying opinions on whether the internet should even be neutral (one comparing it to forcing FedEx and UPS to deliver every package at the same rate) but bigger questions aside, here are some thoughts from those concerned with yesterday’s announcement.
Wireless
Though some say that it’s important not to hamper growing wireless communication, others question if leaving wireless communications out of any regulation plan will have repercussions for a competitive wireless future.
The other big news in today’s announcement was Google’s clear retreat on network neutrality when it comes to wireless networks. As Susan Crawford, professor at Cardozo Law School and an expert on all things Internet, : ”That’s a huge hole, given the growing popularity of wireless services and the recent suggestion by the Commission that we may not have a competitive wireless marketplace.” []
One Equal Internet
Others question if the policy proposal in allowing specialized broadband services faster access may create two “internets”: one internet as we currently know it, and one internet of specialized services, what some have compared to a premium cable version of the net.
Internet meme-sters have long referred to “the internets” as a sort of inside joke, because of course there’s just one internet. But if Google’s and Verizon’s proposal goes through, we really would have two internets–one free, where Google pledges to stay, another paid, where services such as 3D television, remote medical procedures, and bandwidth-intensive games appear–for a price. []
Businesses vs Legislators
Some questions if Google and Verizon should really be proposing these policies (and legislative frameworks) in the first place. Some ask if the FCC should go ahead and reclassify broadband so they can regulate it, though such a movement is certain to bring lawsuits.
[A]ny proposal that Google and Verizon come up with will have to be approved by Congress. It would certainly serve the public interest better if Congress gathered input from more than just two companies and created a proposal of its own. Unfortunately, Congress hasn’t shown much appetite for net neutrality legislation in the past, and we’re not optimistic about the near-term future. So it’s time for the commission to do the right thing and reclassify broadband. Yes, that will mean lawsuits. It will mean that net neutrality has a precarious future. But it has a precarious future right now, and the public can’t afford to wait. []
Unending Discussion
FCC Commissioner Michael J. Copps said in a statement yesterday of the policy plan is that it’s time to move from discussion to decision.
“Some will claim this announcement moves the discussion forward.That’s one of its many problems. It is time to move a decision forward—a decision to reassert FCC authority over broadband telecommunications, to guarantee an open Internet now and forever, and to put the interests of consumers in front of the interests of giant corporations.” []
South Korean police raided the offices of Google Korea on Tuesday to investigate whether the company illegally collected data while it worked on a mapping service.
South Korean police raided the offices of Google Korea on Tuesday to investigate whether the company illegally collected data while it worked on a mapping service.
Lawrence Ellison, the head of Oracle, said Hewlett-Packard’s decision to remove Mark Hurd was not in the best interest of “employees, shareholders, customers and partners.”
P is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.
