Blog: Mario Is Hard, and That's Mathematically Official

Mario Is Hard, and That's Mathematically Official
New Scientist (03/14/12) Jacob Aron

Massachusetts Institute of Technology (MIT) researchers recently analyzed the computational complexity of video games and found that many of them belong to a class of mathematical problems called NP-hard. The implication is that for a given game level, it can be very tough to determine whether it is possible for a player to reach the end. The results suggest that some hard problems could be solved by playing a game. The researchers, led by MIT's Erik Demaine, converted each game into a Boolean satisfiability problem, which asks whether the variables in a collection of logical statements can be chosen to make all the statements true, or whether the statements inevitably contradict each other. For each game, the team built sections of a level that force players to choose one of two paths, which are equal to assigning variables in the Boolean satisfiability problem. If they permit the completion of a level, that is equivalent to all of the statements in the Boolean problem being true. However, if they make completion impossible, it is equal to a contradiction. Many of the games proved to be NP-hard, which means that deciding whether a player can complete them is at least as difficult as the hardest problems in NP.

View Full Article

Blog: The Million-Dollar Puzzle That Could Change the World [determining whether P equals NP]

The Million-Dollar Puzzle That Could Change the World
New Scientist (06/01/11) Jacob Aron

The single biggest problem in computer science, for which the Clay Mathematics Institute is offering a $1 million prize to whoever solves it, is determining whether P equals NP, which raises the issue that computation has a fundamental, innate limitation that goes beyond hardware. The complexity class of NP, or non-deterministic polynomial time, is comprised of problems whose solutions are difficult to come by but can be confirmed in polynomial time. All problems in the set P also can be found in the set NP, but the core of the P=NP? problem is whether the reverse also applies. If P turns out not to be equal to NP, it demonstrates that some problems are so involved naturally that crunching through them is impossible, and validating this theory would gain insight on the performance of the latest computing hardware, which divides computations across multiple parallel processors, says the University of Massachusetts, Amherst's Neil Immerman. The field of cryptography also could be affected by this proof, as even the toughest codes would be cracked by a polynomial-time algorithm for solving NP problems. On the other hand, finding an algorithm to solve an NP-complete problem would enable any NP problem to be solved in polynomial time, establishing a universal computable solution. This could support the creation of algorithms that execute near-perfect speech recognition and language translation, and that facilitate computerized visual information processing equal to that of humans.

View Full Article

Blog: What Does 'P vs. NP' Mean for the Rest of Us?

What Does 'P vs. NP' Mean for the Rest of Us?
Technology Review (08/19/10) Pavlus, John

Although the current consensus is that Hewlett-Packard Labs research scientist Vinay Deolalikar's approach is fundamentally flawed, a verified P versus NP proof would conclusively determine what kinds of problems are and are not computer-solvable. NP-class problems in existence hold significant implications for pattern matching and optimization in a broad area of subjects. Such subjects include the arrangement of transistors on a silicon chip, the development of accurate financial prediction models, and analysis of cellular protein-folding behavior. The P versus NP problem queries whether these two classes are identical, which entails that every NP problem would feature a concealed shortcut permitting computers to rapidly come up with perfect solutions. Proving P is not equal to NP would validate widely accepted assumptions, such as the inability to efficiently factor massive composite numbers that form the foundation of modern cryptography. Still, "even if you proved that P does not equal NP ... it would have to radically expand our understanding of those capabilities, and make many new things possible with computers, in addition to all the clever workarounds we've already found," says Georgia Tech's Richard Lipton.

View Full Article

Blog: Step 1: Post Elusive Proof. Step 2: Watch Fireworks

Step 1: Post Elusive Proof. Step 2: Watch Fireworks
New York Times (08/16/10) Markoff, John

A proposed proof of the P versus NP problem posted by Hewlett-Packard mathematician Vinay Deolalikar posits that P does not equal NP, which implies that there are problems which computers cannot solve yet which have easily recognizable solutions. This is a key underlying precept of modern cryptography. But the proof also is significant for inspiring Internet-based collaboration by complexity theorists and others for the purpose of discussing the proof. The theorists employed blogs and wikis to conduct real-time discussion and analysis of the proof, and this kind of collaboration has emerged only relatively recently in the math and computer science communities. New York University professor Clay Shirky contends in a recently published book, "Cognitive Surplus: Creativity and Generosity in a Connected Age," that the development of these new collaborative tools is fostering a second scientific revolution by ushering in a new paradigm of peer review. "It's not just, 'Hey, everybody, look at this,' but rather a new set of norms is emerging about what it means to do mathematics, assuming coordinated participation," he says.

View Full Article

Blog: HP Researcher Claims to Crack Compsci Complexity Conundrum

HP Researcher Claims to Crack Compsci Complexity Conundrum
IDG News Service (08/09/10) Jackson, Joab

Hewlett-Packard researcher Vinay Deolalikar claims to have solved the computer science problem widely known as P versus NP. In an email to a group of math professors, Deolalikar said he was announcing proof that polynomial time (P) is not equal to nondeterministic polynomial time (NP), which may mean certain problems can only be solved by brute force searching, if solutions can be found at all. Deolalikar said he pieced together principles from multiple areas within mathematics. "The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens," Deolalikar wrote. No one who is familiar with the problem has said Deolalikar has solved it thus far, considering the amount of checking that needs to be done on his solution. The Clay Mathematics Institute has promised to pay $1 million to the person who solves the problem. The P versus NP problem involves "determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," according to the institute.

View Full Article

Blog: Prizes Aside, the P-NP Puzzler Has Consequences

Prizes Aside, the P-NP Puzzler Has Consequences
New York Times (10/08/09) Markoff, John

The frenzy of downloading that accompanied the September cover article in the Communications of the ACM when it was issued online reflects the intense interest in the subject of the article--the progress, or lack thereof, on solving the P vs. NP challenge. P represents the class of problems that can be solved in polynomial time, while NP represents the class of problems that can be confirmed in polynomial time. It is theorized that if P equals NP, some of the most complex real-world computing problems, such as optimizing the layout of transistors on a computer chip, could be addressed, triggering an acceleration of technological and economic productivity. Cracking computer codes raises a similar challenge. Such tasks share the common characteristic that an increase in the size of a problem is accompanied by an exponential increase in the computer time needed to solve it. Progress on meeting the P vs. NP challenge has been slow, but Lance Fortnow of the McCormick School of Engineering at Northwestern University believes the theory might be proved or disproved through algebraic geometry.

View Full Article

Blog: A New Kind of Counting; Graph Coloring Problem solution

A New Kind of Counting
Max Planck Society (02/06/09) Abrell, Barbara

Scientists at Germany's Max Planck Institute for Dynamics and Self-Organization (MPIDS) and Cornell University have developed a computer algorithm to crack previously unsolvable counting problems. Such counting problems are visualized by researchers as a network of lines and nodes, which means only one basic challenge must be met: Determining the number of different ways to color in the nodes with a certain number of colors without assigning the same color to nodes joined by a line. A node's color is imbued with a completely new significance, depending on the application. "The existing algorithm copies the whole network for each stage of the calculation and only changes one aspect of it each time," says MPIDS scientist Frank van Bussel. The researchers move through the network on a node-by-node basis, and the program never looks at the entire network but only at the next node point. At the first node point, the program cannot finalize the color selection as it would have to know how all the other nodes are linked to each other. Instead, the program notes down a formula for the first lattice point, which contains this uncertainty as an unknown quantity. As the program moves through the network, all the connections are exposed and the unknown quantities are removed. The program's knowledge of the network is complete once it has reached the final node point. The calculation time for a square lattice the size of a chess board is estimated to be many billions of years, but Denny Fliegner of MPIDS says the program can accomplish this in just seven seconds.

View Full Article

Research: Accidental Algorithms

Accidental Algorithms
American Scientist (02/08) Vol. 96, No. 1, P. 9; Hayes, Brian
"Holographic" or "accidental" algorithms comprise a new and unanticipated algorithmic family that offers efficient techniques for several problems whose solutions could only previously be worked out by brute-force computation. The algorithms facilitate deeper investigation into the barrier between P problems, which are problems with at least one polynomial-time algorithm, and nondeterministic polynomial (NP) problems. Within the NP class reside NP-complete problems, which stand out by virtue of having a polynomial-time solution that can be adapted to rapidly solve all problems in NP. Problems known to be NP-complete currently number in the thousands, and collectively they form a massive weave of interdependent computations. Harvard University's Leslie G. Valiant says holographic algorithms get their name from the fact that their computational power extends from the mutual cancellation of many contributions to a sum, much like the optical interference pattern responsible for generating a hologram. Holographic reductions tap a class of transformations that do not necessarily connect individual problem instances, but they do retain the number of solutions or the sum of the solutions. This is adequate for certain counting problems.
Click Here to View Full Article

Research: Simplicity Sought for Complex Computing [Wolfram]

Simplicity Sought for Complex Computing
Chicago Tribune (11/19/07) Van, Jon
Stephen Wolfram says people building complex computers and writing complicated software may achieve more studying nature. Wolfram says his company is exploring the "computational universe" to find more simple solutions to complex problems that are currently handled by complex software. "Nature has a secret it uses to make this complicated stuff," Wolfram says. "Traditionally, we're not taking advantage of that secret. We create things that go around things nature is doing." Wolfram believes that nature has created a molecule that could be used as a computer if people ever manage to isolate and program the molecule. University of Chicago Department of Computer Science Chairman Stuart Kurtz says a lot of computer scientists are fascinated by finding simple systems capable of producing complex results. For example, a University of Southern California professor has proposed using recombinant DNA for computing. While DNA computers are largely theoretical, computer scientists take them quite seriously, Kurtz says. "People are used to the idea that making computers is hard," Wolfram says. "But we're saying you can make computers out of small numbers of components, with very simple rules."
Click Here to View Full Article