MIT News - Theoretical computer science
https://news.mit.edu/rss/topic/theoretical-computer-science
MIT news feed about: Theoretical computer scienceenFri, 01 Mar 2013 15:00:03 -0500Short algorithm, long-range consequences
https://news.mit.edu/2013/short-algorithm-long-range-consequences-0301
A new technique for solving ‘graph Laplacians’ is drastically simpler than its predecessors, with implications for a huge range of practical problems.Fri, 01 Mar 2013 15:00:03 -0500https://news.mit.edu/2013/short-algorithm-long-range-consequences-0301Larry Hardesty, MIT News Office<p>In the last decade, theoretical computer science has seen remarkable progress on the problem of solving graph Laplacians — the esoteric name for a calculation with hordes of familiar applications in scheduling, image processing, online product recommendation, network analysis, and scientific computing, to name just a few. Only in 2004 did researchers first propose an algorithm that solved graph Laplacians in “nearly linear time,” meaning that the algorithm’s running time didn’t increase exponentially with the size of the problem.<br />
</p>
<div class="video_captions" style="width: 368px; float: right; margin: 0 0 10px 10px;"><img src="/sites/default/files/images/inline/images/2013/laplacians.gif" style="border-width: 0px; border-style: solid; width: 368px;" /> <span class="image_caption">This animation shows two different "spanning trees" for a simple graph, a grid like those used in much scientific computing. The speedups promised by a new MIT algorithm require "low-stretch" spanning trees (green), in which the paths between neighboring nodes don't become excessively long (red).</span> <span class="image_credit">Images courtesy of the researchers</span></div>
<p>At this year’s ACM Symposium on the Theory of Computing, MIT researchers will present <a href="http://arxiv.org/pdf/1301.6628" target="_blank">a new algorithm</a> for solving graph Laplacians that is not only faster than its predecessors, but also drastically simpler. “The 2004 paper required fundamental innovations in multiple branches of mathematics and computer science, but it ended up being split into three papers that I think were 130 pages in aggregate,” says Jonathan Kelner, an associate professor of applied mathematics at MIT who led the new research. “We were able to replace it with something that would fit on a blackboard.”<br />
<br />
The MIT researchers — Kelner; Lorenzo Orecchia, an instructor in applied mathematics; and Kelner’s students Aaron Sidford and Zeyuan Zhu — believe that the simplicity of their algorithm should make it both faster and easier to implement in software than its predecessors. But just as important is the simplicity of their conceptual analysis, which, they argue, should make their result much easier to generalize to other contexts.<br />
<br />
<strong>Overcoming resistance</strong><br />
<br />
A graph Laplacian is a matrix — a big grid of numbers — that describes a <a href="/newsoffice/2012/explained-graphs-computer-science-1217.html" target="_blank">graph</a>, a mathematical abstraction common in computer science. A graph is any collection of nodes, usually depicted as circles, and edges, depicted as lines that connect the nodes. In a logistics problem, the nodes might represent tasks to be performed, while in an online recommendation engine, they might represent titles of movies.<br />
<br />
In many graphs, the edges are “weighted,” meaning that they have different numbers associated with them. Those numbers could represent the cost — in time, money or energy — of moving from one step to another in a complex logistical operation, or they could represent the strength of the correlations between the movie preferences of customers of an online video service.<br />
<br />
The Laplacian of a graph describes the weights between all the edges, but it can also be interpreted as a series of linear equations. Solving those equations is crucial to many techniques for analyzing graphs.<br />
<br />
One intuitive way to think about graph Laplacians is to imagine the graph as a big electrical circuit and the edges as resistors. The weights of the edges describe the resistance of the resistors; solving the Laplacian tells you how much current would flow between any two points in the graph.<br />
<br />
Earlier approaches to solving graph Laplacians considered a series of ever-simpler approximations of the graph of interest. Solving the simplest provided a good approximation of the next simplest, which provided a good approximation of the next simplest, and so on. But the rules for constructing the sequence of graphs could get very complex, and proving that the solution of the simplest was a good approximation of the most complex required considerable mathematical ingenuity.<br />
<br />
<strong>Looping back</strong><br />
<br />
The MIT researchers’ approach is much more straightforward. The first thing they do is find a “spanning tree” for the graph. A tree is a particular kind of graph that has no closed loops. A family tree is a familiar example; there, a loop might mean that someone was both parent and sibling to the same person. A spanning tree of a graph is a tree that touches all of the graph’s nodes but dispenses with the edges that create loops. Efficient algorithms for constructing spanning trees are well established.<br />
<br />
The spanning tree in hand, the MIT algorithm then adds back just one of the missing edges, creating a loop. A loop means that two nodes are connected by two different paths; on the circuit analogy, the voltage would have to be the same across both paths. So the algorithm sticks in values for current flow that balance the loop. Then it adds back another missing edge and rebalances.<br />
<br />
In even a simple graph, values that balance one loop could imbalance another one. But the MIT researchers showed that, remarkably, this simple, repetitive process of adding edges and rebalancing will converge on the solution of the graph Laplacian. Nor did the demonstration of that convergence require sophisticated mathematics: “Once you find the right way of thinking about the problem, everything just falls into place,” Kelner explains.<br />
<br />
<strong>Paradigm shift</strong><br />
<br />
Daniel Spielman, a professor of applied mathematics and computer science at Yale University, was Kelner’s thesis advisor and one of two co-authors of the 2004 paper. According to Spielman, his algorithm solved Laplacians in nearly linear time “on problems of astronomical size that you will never ever encounter unless it’s a much bigger universe than we know. Jon and colleagues’ algorithm is actually a practical one.”<br />
<br />
Spielman points out that in 2010, researchers at Carnegie Mellon University also presented a practical algorithm for solving Laplacians. Theoretical analysis shows that the MIT algorithm should be somewhat faster, but “the strange reality of all these things is, you do a lot of analysis to make sure that everything works, but you sometimes get unusually lucky, or unusually unlucky, when you implement them. So we’ll have to wait to see which really is the case.”<br />
<br />
The real value of the MIT paper, Spielman says, is in its innovative theoretical approach. “My work and the work of the folks at Carnegie Mellon, we’re solving a problem in numeric linear algebra using techniques from the field of numerical linear algebra,” he says. “Jon’s paper is completely ignoring all of those techniques and really solving this problem using ideas from data structures and algorithm design. It’s substituting one whole set of ideas for another set of ideas, and I think that’s going to be a bit of a game-changer for the field. Because people will see there’s this set of ideas out there that might have application no one had ever imagined.”</p>
Image courtesy of the researchersDemaine named Presburger Award recipient
https://news.mit.edu/2013/demaine-named-presburger-award-recipient
Professor Erik Demaine was cited for his contributions to computational geometry and data structures.Mon, 25 Feb 2013 18:55:00 -0500https://news.mit.edu/2013/demaine-named-presburger-award-recipientCSAILErik Demaine, a professor of electrical engineering and computer science, has been honored with the 2013 European Association for Theoretical Computer Science (EATCS) Presburger Award for young scientists.<br /><br />Demaine was selected for his “outstanding contributions in several fields of algorithms, namely computational geometry, data structures, graph algorithms and recreational algorithms,” according to the EATCS website. “His work has shown promising applications to computer graphics, sensor networks, molecular biology, programmable matter, and manufacturing and engineering.”<br /><br />Demaine was cited for his work in computational geometry and data structures, where he has made progress on classical problems such as the carpenter’s rule problem, the hinged-dissection problem, the prefix-sum problem and the dynamic optimality conjecture. He is also credited with starting the field of computational origami with his book on the theory of folding.<br /><br />Demaine, a MacArthur Fellow and Alfred P. Sloan Research Fellow, is a member of the Theory of Computation and the Algorithms groups at CSAIL. An accomplished artist, his interests include origami and glassblowing. Several of his curved origami sculptures are housed in the permanent collection at the Museum of Modern Art in New York.<br /><br />Since 2010, EATCS has presented the Presburger Award to a young scientist for outstanding contributions in theoretical computer science. The award is named after Mojzesz Presburger, who accomplished his work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.<br /><br />Demaine will be presented with the Presburger Award at the annual International Colloquium on Automata, Languages and Programming (ICALP), held in Latvia in July.<br />Erik DemainePhoto courtesy of CSAILProving quantum computers feasible
https://news.mit.edu/2012/proving-quantum-computers-feasible-1127
With a new contribution to probability theory, researchers show that relatively simple physical systems could yield powerful quantum computers.Tue, 27 Nov 2012 05:00:02 -0500https://news.mit.edu/2012/proving-quantum-computers-feasible-1127Larry Hardesty, MIT News OfficeQuantum computers are devices — still largely theoretical — that could perform certain types of computations much faster than classical computers; one way they might do that is by exploiting “spin,” a property of tiny particles of matter. A “spin chain,” in turn, is a standard model that physicists use to describe systems of quantum particles, including some that could be the basis for quantum computers.<br /><br />Many quantum algorithms require that particles’ spins be “entangled,” meaning that they’re all dependent on each other. The more entanglement a physical system offers, the greater its computational power. Until now, theoreticians have demonstrated the possibility of high entanglement only in a very complex spin chain, which would be difficult to realize experimentally. In simpler systems, the degree of entanglement appeared to be capped: Beyond a certain point, adding more particles to the chain didn’t seem to increase the entanglement.<br /><br />This month, however, in the journal <i>Physical Review Letters</i>, a group of researchers at MIT, IBM, Masaryk University in the Czech Republic, the Slovak Academy of Sciences and Northeastern University proved that even in simple spin chains, <a href="http://prl.aps.org/abstract/PRL/v109/i20/e207202" target="_blank">the degree of entanglement scales with the length of the chain</a>. The research thus offers strong evidence that relatively simple quantum systems could offer considerable computational resources.<br /><br />In quantum physics, the term “spin” describes the way that tiny particles of matter align in a magnetic field: A particle with spin up aligns in one direction, a particle with spin down in the opposite direction. But subjecting a particle to multiple fields at once can cause it to align in other directions, somewhere between up and down. In a complex enough system, a particle might have dozens of possible spin states.<br /><br />A spin chain is just what it sounds like: a bunch of particles in a row, analyzed according to their spin. A spin chain whose particles have only two spin states exhibits no entanglement. But in the new paper, MIT professor of mathematics Peter Shor, his former student Ramis Movassagh, who is now an instructor at Northeastern, and their colleagues showed that unbounded entanglement is possible in chains of particles with only three spin states — up, down and none. Systems of such particles should, in principle, be much easier to build than those whose particles have more spin states.<br /><br /><strong>Tangled up</strong><br /><br />The phenomenon of entanglement is related to the central mystery of quantum physics: the ability of a single particle to be in multiple mutually exclusive states at once. Electrons, photons and other fundamental particles can, in some sense, be in more than one place at the same time. Similarly, they can have more than one spin at once. If you try to measure the location, spin or some other quantum property of a particle, however, you’ll get a definite answer: The particle will snap into just one of its possible states.<br /><br />If two particles are entangled, then performing a measurement on one tells you something about the other. For instance, if you measure the spin of an electron orbiting a helium atom, and its spin is up, the spin of the other electron in the same orbit must be down, and vice versa. For a chain of particles to be useful for quantum computing, all of their spins need to be entangled. If, at some point, adding more particles to the chain ceases to increase entanglement, then it also ceases to increase computational capacity.<br /><br />To show that entanglement increases without bound in chains of three-spin particles, the researchers proved that any such chain with a net energy of zero could be converted into any other through a small number of energy-preserving substitutions. The proof is kind of like one of those puzzles where you have to convert one word into another of the same length, changing only one letter at a time.<br /><br />“Energy preserving” just means that changing the spins of two adjacent particles doesn’t change their total energy. For instance, if two adjacent particles have spin up and spin down, they have the same energy as two adjacent particles with no spin. Similarly, swapping the spins of two adjacent particles leaves their energy the same. Here, the “puzzle” is to convert one spin chain into another using only these and a couple of other substitutions.<br /><br /><strong>No bottlenecks</strong><br /><br />If you envision every set of definite spins for a chain of three-spin particles as a point in space, and draw lines only between those that that are interchangeable using energy-preserving substitutions, then you end up with a well-connected network. <br /><br />“If you want to go from any state to another state, it has high conductivity,” Movassagh says. “It’s like, if you have a town with a bunch of alleys, and you want to go from any neighborhood to any other, you can only go rapidly if there’s no one road that’s necessary to use and congested.” To prove that, in systems of three-spin particles, transitions between sets of spin were possible through these “back alleys,” Movassagh says, “we proved something that we think is new in probability theory.”<br /><br />“It’s been known that if the particles can have constant but rather high dimension” — that is, number of possible spin states — “the entanglement can be pretty high,” says Sandy Irani, a professor of computer science at the University of California at Irvine who specializes in quantum computation. “But the requirement is that these little particles have something like dimension 14, 15, 16. In terms of what people are actually looking at experimentally, they’re looking at very low-dimensional things. Having particles of dimension of 15, 16, is much more difficult to bring about in the lab.” <br /><br />Shor, Movassagh and their colleagues, Irani says, “have shown that if you just step up from two to three, the entanglement can actually grow with the number of particles.”<br /><br />Irani cautions, however, that the new paper shows only that entanglement scales logarithmically with the length of the spin chain. “If you go up to these larger-dimension particles, in the teens, you get entanglement that can scale with the number of particles instead of the log of the number of particles,” she says, “and that may be required for quantum computing.”The possible quantum states of a chain of particles can be represented as points in space, with lines connecting states that can be swapped with no change in the chain's total energy. MIT researchers and their colleagues
showed that such networks are densely interconnected, with heavily trafficked pathways between points.Graphic: Christine Daniloff10-year-old problem in theoretical computer science falls
https://news.mit.edu/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731
Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.Tue, 31 Jul 2012 04:00:00 -0400https://news.mit.edu/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731Larry Hardesty, MIT News Office<div class="video_captions"><img src="/sites/default/files/images/inline/newsofficeimages/vidick.jpg" border="0" /><br /><strong>Thomas Vidick</strong><br /><i>Photo: M. Scott Brauer</i><br /><br /></div>
<div class="video_captions" style="float: left; padding: 10px 10px 10px 0px; width: 150px;"><img src="/sites/default/files/images/inline/newsofficeimages/best-of-2012.jpg" border="0" alt="Best of 2012" /></div>
Interactive proofs, which MIT researchers helped pioneer, have emerged as one of the major research topics in theoretical computer science. In the classic interactive proof, a questioner with limited computational power tries to extract reliable information from a computationally powerful but unreliable respondent. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they’re just as important for the insight they provide into the complexity of computational problems.<br /><br />Twenty years ago, researchers showed that if the questioner in an interactive proof is able to query multiple omniscient respondents — which are unable to communicate with each other — it can extract information much more efficiently than it could from a single respondent. As <a href="http://www.technologyreview.com/mitnews/424362/the-quantum-frontier/" target="_blank">quantum computing</a> became a more popular research topic, however, computer scientists began to wonder whether such multiple-respondent — or “multiprover” — systems would still work if the respondents were able to perform measurements on physical particles that were “entangled,” meaning that their quantum properties were dependent on each other.<br /><br />At the IEEE Symposium on Foundations of Computer Science in October, Thomas Vidick, a postdoc at MIT’s Computer Science and Artificial Intelligence Laboratory, and Tsuyoshi Ito, a researcher at NEC Labs in Princeton, N.J., <a href="http://xxx.lanl.gov/abs/1207.0550" target="_blank">finally answer that question</a>: Yes, there are multiprover interactive proofs that hold up against entangled respondents. That answer is good news for cryptographers, but it’s bad news for quantum physicists, because it proves that there’s no easy way to devise experiments that illustrate the differences between classical and quantum physical systems.<br /><br />It’s also something of a surprise, because when the question was first posed, it was immediately clear that some multiprover proofs were not resilient against entanglement. Vidick and Ito didn’t devise the proof whose resilience they prove, but they did develop new tools for analyzing it.<br /><br /><strong>Boxed in</strong><br /><br />In an interactive proof, a questioner asks a series of questions, each of which constrains the range of possible answers to the next question. The questioner doesn’t have the power to compute valid answers itself, but it does have the power to determine whether each new answer meets the constraints imposed by the previous ones. After enough questions, the questioner will either expose a contradiction or reduce the probability that the respondent is cheating to near zero.<br /><br />Multiprover proofs are so much more efficient than single-respondent proofs because none of the respondents knows the constraints imposed by the others’ answers. Consequently, contradictions are much more likely if any respondent tries to cheat.<br /><br />But if the respondents have access to particles that are entangled with each other — say, electrons that were orbiting the same atom but were subsequently separated — they can perform measurements — of, say, the spins of select electrons — that will enable them to coordinate their answers. That’s enough to thwart some interactive proofs.<br /><br />The proof that Vidick and Ito analyzed is designed to make cheating difficult by disguising the questioner’s intent. To get a sense of how it works, imagine a graph that in some sense plots questions against answers, and suppose that the questioner is interested in two answers, which would be depicted on the graph as two points. Instead of asking the two questions of interest, however, the questioner asks at least three different questions. If the answers to those questions fall on a single line, then so do the answers that the questioner really cares about, which can now be calculated. If the answers don’t fall on a line, then at least one of the respondents is trying to cheat.<br /><br />“That’s basically the idea, except that you do it in a much more high-dimensional way,” Vidick says. “Instead of having two dimensions, you have ‘N’ dimensions, and you think of all the questions and answers as being a small, N-dimensional cube.”<br /><strong><br />Gaining perspective</strong><br /><br />This type of proof turns out to be immune to quantum entanglement. But demonstrating that required Vidick and Ito to develop a new analytic framework for multiprover proofs. <br /><br />According to the weird rules of quantum mechanics, until a measurement is performed on a quantum particle, the property being measured has no definite value; measuring snaps the particle into a definite state, but that state is drawn randomly from a probability distribution of possible states.<br /><br />The problem is that, when particles are entangled, their probability distributions can’t be treated separately: They’re really part of a single big distribution. But any mathematical description of that distribution supposes a bird’s-eye perspective that no respondent in a multiprover proof would have. Finding a way to do justice to both the connection between the measurements and the separation of the measurers proved enormously difficult. “It took Tsuyoshi and me about a year and a half,” Vidick says. “But in fact, one could say I’ve been working on this since 2006. My very first paper was on exactly the same topic.”<br /><br />Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito’s paper is the quantum analogue of an earlier paper on multiprover interactive proofs that “basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years.” Similarly, she says, the new paper “could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory.”<br /><br />The paper could also have implications for physics, Aharonov adds. “This is a step toward deepening our understanding of the notion of entanglement, and of things that happen in quantum systems — correlations in quantum systems, and efficient descriptions of quantum systems, et cetera,” she says. “But it’s very indirect. This looks like an important step, but it’s a long journey.”<br />Thomas VidickPhoto: M. Scott BrauerDueling algorithms
https://news.mit.edu/2011/dueling-algorithms-0318
If software companies design their algorithms with the sole intention of outperforming each other, the customer can be the loser.Fri, 18 Mar 2011 04:00:01 -0400https://news.mit.edu/2011/dueling-algorithms-0318Larry Hardesty, MIT News OfficeThere’s an old joke about two hikers on a trail, one wearing hiking boots and the other running shoes. “Why the running shoes?” the first hiker asks. “In case of bears,” the second answers. The first hiker laughs and says, “Running shoes won’t help you outrun a bear.” “I don’t need to beat the bear,” the second hiker says. “I just need to beat you.”<br /><br />When computer scientists design algorithms, they’re generally concerned with providing the best possible answer in the shortest amount of time. But for a web company in a competitive market, the best algorithm might just be the one that beats the other guy. At the Association for Computing Machinery’s 43rd Annual Symposium on Theory of Computing in June, Ankur Moitra, a PhD student in the Computer Science and Artificial Intelligence Laboratory, and colleagues will <a href="http://arxiv.org/pdf/1101.2883v1" target="_blank">present a new mathematical framework</a> for analyzing such “dueling algorithms.” The work could help answer questions such as when competition between web services helps meet social ends and when it undermines them, and it could also prove useful in the social sciences.<br /><br />To understand the idea of dueling algorithms, Moitra says, consider a search engine ranking the results of a query. The words of the query could be subject to multiple interpretations: “Cambridge,” for instance, could refer to several different cities. Suppose that in using a given search term, 40 percent of people mean one thing, 30 percent a second and 30 percent a third. A computer scientist designing a search algorithm in the abstract would probably prioritize the most likely interpretation. But in a commercial market, if that’s what the leading search engine does, a competitor might do well to prioritize the other two. Forty percent of its customers will be disappointed, but the other 60 percent will prefer the results they get to those provided by the market leader.<br /><br />Of course, the leader is unlikely to sit idle as the upstart steals its business. So it might evolve some hybrid ranking strategy, sprinkling some of the less likely interpretations among its top results. That, in turn, would prompt the competitors to revise their strategies, which would prompt another revision from the leader, and so on. Ultimately, the theory goes, the competitors in the market will converge on what economists call an equilibrium, a state in which no competitor has any incentive to change its strategy unilaterally. Any given contest could have many equilibria; which one emerges depends on how the contestants’ strategies evolve over time.<br /><br /><strong>Balance of power</strong><br /><br />Moitra and his colleagues at Northwestern University, the University of Toronto, the University of Pennsylvania, Israel’s Technion and Microsoft Research have developed methods for finding equilibrium strategies much more efficiently than was previously possible, at least for two-player, winner-take-all contests. Even these simple contests, however, yield enormously complex calculations. Finding equilibria generally requires comparing all possible strategies against each other. In the search engine example, that would mean comparing every ordering of search results against every other ordering. As the number of results gets larger, the complexity of the comparison increases exponentially.<br /><br />For several different types of contest, however, Moitra and his colleagues found ways to represent the results of different strategies probabilistically. That makes it much easier to calculate equilibria, but the strategies found to be in equilibrium are defined only by their statistics. So the researchers also had to provide computational methods for finding specific sets of strategies that match the statistical profiles of the equilibrium calculation.<br /><br />In their paper, the researchers consider several cases of dueling algorithms. Among them are two computers searching for an item in a database, two companies trying to hire employees from the same pool of applicants, and two racers trying to plot routes across a town with erratic traffic patterns. In each case they find that an equilibrium strategy for beating an opponent may not be a good strategy in the abstract: the company may not end up with the best possible employees, for instance, and the computer may not find the item in the database as efficiently as it could.<br /><br />According to Eva Tardos, Jacob Gould Schurman Professor of Computer Science at Cornell University, the researchers’ paper “is more the beginning of research than a definitive result or end product.” The researchers’ models make several simplifying assumptions — including the number of competitors — that make the math easier but limit their applicability. Nonetheless, “just raising the questions is an important step forward,” Tardos says. “With traditional optimization, you just want the algorithm to be as good as possible, versus wanting to beat the opponent. Clearly, there’s a tension between these goals. I think they are setting a research agenda to understand this tension.”<br /><br />Ankur Moitra, a PhD student in the Computer Science and Artificial Intelligence Laboratory.Photo: Patrick Gillooly3 questions: P vs. NP
https://news.mit.edu/2010/3q-pnp
After glancing over a 100-page proof that claimed to solve the biggest problem in computer science, Scott Aaronson bet his house that it was wrong. Why?Tue, 17 Aug 2010 04:00:01 -0400https://news.mit.edu/2010/3q-pnpLarry Hardesty, MIT News Office<p>On Friday, Aug. 6, a mathematician at HP Labs named Vinay Deolalikar sent an e-mail to a host of other researchers with a <a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated_1.pdf" target="_blank">103-page attachment</a> that purported to answer the most important outstanding question in computer science. That question is whether P = NP, and answering it will earn you $1 million from the Clay Mathematics Institute.<br />
<br />
Last fall, MIT News published a <a href="/newsoffice/2009/explainer-pnp.html">fairly detailed explanation</a> of what P = NP means. But roughly speaking, P is a set of relatively easy problems, NP includes a set of incredibly hard problems, and if they’re equal, then a large number of computer science problems that seem to be incredibly hard are actually relatively easy. Problems in NP include the factoring of large numbers, the selection of an optimal route for a traveling salesman, and the so-called 3-SAT problem, in which you must find values that satisfy triplets of logical conditions. For instance, is it possible to contrive an attendance list for a party that satisfies the triplet (Alice OR Bob AND Carol) AND (David AND Ernie AND NOT Alice)? (Yes: Bob, Carol, David, and Ernie were there, but Alice wasn’t.) Interestingly, the related 2-SAT problem — which instead uses pairs of conditions, like (Alice OR Ernie) — is in the set of easy problems, P, as is the closely related XOR-SAT problem.<br />
<br />
Most computer scientists believe that P doesn’t equal NP, and that’s what Deolalikar claimed to have proved. But by the following Monday, despite being on vacation in the Mediterranean and having time only to glance through the proof, MIT Associate Professor of Electrical Engineering and Computer Science Scott Aaronson had announced on his blog that he would mortgage his house and chip in another $200,000 if Deolalikar’s proof was correct. Last week, Aaronson took a few minutes to answer three questions about P and NP.<br />
<br />
<strong>Q. </strong>Has the proof now been shown conclusively to be wrong?<br />
<br />
<strong>A. </strong>I would say yeah. It was clear a couple days ago that there was a very serious gap in the statistical-physics part of the argument. It was not clear at all that the argument for showing why an NP-complete problem like 3-SAT was hard wouldn’t also show that problems like XOR-SAT are hard. Now, XOR-SAT is a variant of this satisfiability problem, which is known to be in P, which has an efficient solution. So if you’re proving that a problem is hard, but your proof could also be adapted to show that an easy problem is hard, then your proof must be fallacious: it proves too much. That’s the first check that people look for when someone announces a proof of P not equal to NP. Why doesn’t it also work for the easy problems?<br />
<br />
The problem with saying that the thing has been conclusively refuted is that whenever anyone points to a problem like this, Vinay Deolalikar has been tending to respond, “Oh, yeah, sure, well, I’m going to address that in my next draft.” So it’s kind of a moving target. But I think it’s absolutely clear right now that at least the existing version does not solve the problem and furthermore wouldn’t solve the problem without some very, very major new ideas.<br />
<br />
<strong>Q. </strong>Why were you so certain that there was a flaw in the proof?<br />
<br />
<strong>A. </strong>P vs. NP is an absolutely enormous problem, and one way of seeing that is that there are already vastly, vastly easier questions that would be implied by P not equal to NP but that we already don’t know how to answer. So basically, if someone is claiming to prove P not equal to NP, then they’re sort of jumping 20 or 30 nontrivial steps beyond what we know today. So the first thing you look for is, What about steps one, two, and three? Can he explain even the easier questions, how he’s answering those? So I looked at the manuscript, and I didn’t see that.<br />
<br />
The other check is the one that I already mentioned, which is, Why does the proof fail for variants of NP-complete problems which are known to be easy? What Deolalikar was doing is, he’s trying to argue that 3-SAT is hard by looking at its statistical properties. The problem is that 2-SAT and XOR-SAT, the problems that are easy, have very, very similar statistical properties, so it did not look like something that could distinguish the hard problems from the easy ones.<br />
<br />
We have very strong reasons to believe that these problems cannot be solved without major — enormous — advances in human knowledge. So you look at the paper and you don’t see that it’s commensurate with the scale of the problem that it’s claiming to solve. This is not a problem that’s going to be solved by just combining or pushing around the ideas that we already have.<br />
<br />
<strong>Q. </strong>Given that most people are pretty confident that P does not equal NP, what would the proof really do for us?<br />
<br />
<strong>A. </strong>Yes, almost all of us believe already that P is not equal to NP. But this is one of those things where it’s not so much the destination as the journey. It’s the massive amount of new understanding of computation that’s going to be needed to prove such a statement. What are we trying to prove? That for solving all these natural optimization problems, or these search problems, or a proof of a theorem, finding the best schedule for airlines, breaking cryptographic codes — all these different things, that there’s no algorithm, no matter how clever, that’s going to solve them feasibly. So in order to prove such a thing, a prerequisite to it is to understand the space of all possible efficient algorithms. That is an unbelievably tall order. So the expectation is that on the way to proving such a thing, we’re going to learn an enormous amount about efficient algorithms, beyond what we already know, and very, very likely discover new algorithms that will likely have applications that we can’t even foresee right now.<br />
<br />
Often in the history of theoretical computer science, the same ideas that you use to prove that something’s impossible can then be turned around to show that something else is possible, and vice versa. The simplest example of that is in cryptography, where you show some problem is hard to solve, and that gives you a code that is useful. But there are many other examples.<br />
</p>
Explained: P vs. NP
https://news.mit.edu/2009/explainer-pnp
The most notorious problem in theoretical computer science remains open, but the attempts to solve it have led to profound insights.Thu, 29 Oct 2009 04:02:00 -0400https://news.mit.edu/2009/explainer-pnpLarry Hardesty, MIT News Office<p><i>Science and technology journalists pride themselves on the ability to explain complicated ideas in accessible ways, but there are some technical principles that we encounter so often in our reporting that paraphrasing them or writing around them begins to feel like missing a big part of the story. So in a new series of articles called "Explained," MIT News Office staff will explain some of the core ideas in the areas they cover, as reference points for future reporting on MIT research.</i><br />
<br />
In the 1995 Halloween episode of <i>The Simpsons</i>, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.<br />
<br />
In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set that includes what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.<br />
<br />
Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.<br />
<br />
Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N<sup>2</sup>, or N times the logarithm of N, or the like.<br />
<br />
A mathematical expression that involves N’s and N<sup>2</sup>s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N's.<br />
<br />
Obviously, an algorithm whose execution time is proportional to N<sup>3</sup> is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2<sup>N</sup>.<br />
<br />
If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N<sup>3</sup> takes almost three hours. But an algorithm whose execution time is proportional to 2<sup>N</sup> takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.<br />
<br />
NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous exponential-time problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.<br />
<br />
So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?<br />
<br />
Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.<br />
<br />
“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.<br />
<br />
Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter's breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.<br />
<br />
Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”<br />
<br />
But if, as Sipser says, “complexity adds a new wrinkle on old problems” in mathematics, it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”<br />
<br />
Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an algorithm that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”</p>