'Hard' NP-complete computer problems explained

August 12, 1999

Believe it or not, there are some problems computers just can't solve -- at least not quickly enough to be of any use.

Many of them are of the type computer scientists call "combinatorial" in which the computer has to try out a vast number of different combinations, as in arranging a sports schedule or planning airline flights. Sometimes the computer does just fine until the problem grows past a certain size: add just one more team, or even one more airline passenger, and the time the computer needs to find a solution suddenly becomes excessively long.

Now an international group of physicists and computer scientists has explained why, and their answer may lead to ways to make some of the hard problems easier. The group published their findings in the July 8, 1999, issue of Nature.

The calculations computer programs make can be described by mathematical formulas, and in combinatorial problems some of those formulas look like the mathematics physicists use to describe a "phase transition" in which a substance or a process undergoes a major change. The most familiar example of a phase transition is the change that water undergoes when it freezes into ice. Both "hard" and "easy" problems can show phase transitions, but the research group shows that the "hard" problems are those in which the phase transition is "discontinuous."

"All phase changes are, in a sense, abrupt," says Bart Selman, Cornell University professor of computer science and the lead computer scientist in the group, "but some are more abrupt than others." A "continuous" transition, he explains, might be represented by a line on a graph that goes along horizontally for a while, then drops rapidly before resuming its horizontal course. In a "discontinuous" transition the line simply breaks and reappears somewhere else.

When there is a continuous phase change, the group found, the time needed to solve the problem simply increases in proportion to the number of new elements added. But if the change is discontinuous the time increases explosively -- in mathematical terms, exponentially -- with the number or elements, making it impractical to solve even moderate sized problems.

The work applies to a class of problems known as "NP-complete," a classification that grows out of analyzing the mathematical function that represents the program. You can prove mathematically that the solution to an NP-complete problem will be correct, but on a practical level it may take hours or days of computer time to find that solution in the worst cases. Thousands of different problems have been shown to be NP-complete, and if an efficient way could be found to solve one, it would apply to all. It has been assumed that no such efficient solution exists, but the new work might show ways to get around that, at least in many practical applications.

"This could make the hard problems easier," Selman says "There are some properties of these abrupt phase transitions that we may be able to exploit. Scheduling problems, for example, are very hard, but the hardness arises out of certain destinations that are hard to schedule. If you get certain critical destinations right, the rest of the problem is easy."

One of the reasons hard problems take so long, the group said in its paper, is that a computer making random choices might lock in some of the critical variables with the wrong values, then spend a tremendous amount of time trying combinations with those values, none of which will work. Instead, the authors suggest nailing down problematic variables before giving the problem to the computer. Tell it the plane always has to land in Chicago, no matter where else it goes or how many people it carries.

Worst cases also occur right at the phase transition, Selman adds. In the real world, this happens where the constraints and resources converge, as for example when an airline has just enough planes to handle all the passengers, or a cellular phone system has just enough frequencies for all its calls. Selman is working on designing systems that will be "just to the left" of that critical point, he says.

The paper in Nature is "Determining computational complexity from characteristic 'phase transitions,' " by Réme Monasson, Ricardo Zecchina, Scott Kirkpatrick, Bart Selman and Lidror Troyansky.

Related World Wide Web sites: The following sites provide additional information on this news release. Some might not be part of the Cornell University community, and Cornell has no control over their content or availability.

-- Bart Selman's home page: http://www.cs.cornell.edu/home/sel man/

-- Nature: http://www.nature.com/

-- Related New York Times article: http://www.nytimes.com/library/national/science/07 1399sci-satisfiability-problems.html

Cornell University

Related Computer Articles from Brightsurf:

UCLA computer scientists set benchmarks to optimize quantum computer performance
Two UCLA computer scientists have shown that existing compilers, which tell quantum computers how to use their circuits to execute quantum programs, inhibit the computers' ability to achieve optimal performance.

Digitize your dog into a computer game
Researchers from CAMERA at the University of Bath have developed motion capture technology that enables you to digitise your dog without a motion capture suit and using only one camera.

Stabilizing brain-computer interfaces
Researchers from Carnegie Mellon University (CMU) and the University of Pittsburgh (Pitt) have published research in Nature Biomedical Engineering that will drastically improve brain-computer interfaces and their ability to remain stabilized during use, greatly reducing or potentially eliminating the need to recalibrate these devices during or between experiments.

Computer-generated genomes
Professor Beat Christen, ETH Zurich to speak in the AAAS 2020 session, 'Synthetic Biology: Digital Design of Living Systems.' Christen will describe how computational algorithms paired with chemical DNA synthesis enable digital manufacturing of biological systems up to the size of entire microbial genomes.

Computer-based weather forecast: New algorithm outperforms mainframe computer systems
The exponential growth in computer processing power seen over the past 60 years may soon come to a halt.

A computer that understands how you feel
Neuroscientists have developed a brain-inspired computer system that can look at an image and determine what emotion it evokes in people.

Computer program looks five minutes into the future
Scientists from the University of Bonn have developed software that can look minutes into the future: The program learns the typical sequence of actions, such as cooking, from video sequences.

Computer redesigns enzyme
University of Groningen biotechnologists used a computational method to redesign aspartase and convert it to a catalyst for asymmetric hydroamination reactions.

Mining for gold with a computer
Engineers from Texas A&M University and Virginia Tech report important new insights into nanoporous gold -- a material with growing applications in several areas, including energy storage and biomedical devices -- all without stepping into a lab.

Teaching quantum physics to a computer
An international collaboration led by ETH physicists has used machine learning to teach a computer how to predict the outcomes of quantum experiments.

Read More: Computer News and Computer Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.