Featured Research

from universities, journals, and other organizations

Can "Hard" Computer Problems, Like Scheduling, Be Made Easier? Cornell-Led Research Team Believes It Knows How

Date:
August 13, 1999
Source:
Cornell University
Summary:
Believe it or not, there are some problems computers just can't solve -- at least not quickly enough to be of any use. 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.

ITHACA, N.Y. -- 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/selman/

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

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


Story Source:

The above story is based on materials provided by Cornell University. Note: Materials may be edited for content and length.


Cite This Page:

Cornell University. "Can "Hard" Computer Problems, Like Scheduling, Be Made Easier? Cornell-Led Research Team Believes It Knows How." ScienceDaily. ScienceDaily, 13 August 1999. <www.sciencedaily.com/releases/1999/08/990813003727.htm>.
Cornell University. (1999, August 13). Can "Hard" Computer Problems, Like Scheduling, Be Made Easier? Cornell-Led Research Team Believes It Knows How. ScienceDaily. Retrieved September 1, 2014 from www.sciencedaily.com/releases/1999/08/990813003727.htm
Cornell University. "Can "Hard" Computer Problems, Like Scheduling, Be Made Easier? Cornell-Led Research Team Believes It Knows How." ScienceDaily. www.sciencedaily.com/releases/1999/08/990813003727.htm (accessed September 1, 2014).

Share This




More Computers & Math News

Monday, September 1, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Apple's Rumored iWatch Could Cost $400

Apple's Rumored iWatch Could Cost $400

Newsy (Aug. 31, 2014) Apple is expected to charge a premium for its still-rumored wearable device. Video provided by Newsy
Powered by NewsLook.com
Amazon Chases Netflix And HBO With Five New Pilots

Amazon Chases Netflix And HBO With Five New Pilots

Newsy (Aug. 31, 2014) Amazon has released another batch of five pilots, allowing viewers to vote on which shows will get full seasons on the company's streaming service. Video provided by Newsy
Powered by NewsLook.com
Apple Wants Your iPhone To Become Your Wallet

Apple Wants Your iPhone To Become Your Wallet

Newsy (Aug. 31, 2014) Apple might soon announce a feature that would allow iPhones to act as a credit card when making payments in physical stores. Video provided by Newsy
Powered by NewsLook.com
Young Entrepreneurs Get $100,000, If They Quit School

Young Entrepreneurs Get $100,000, If They Quit School

AFP (Aug. 29, 2014) Twenty college-age students are getting 100,000 dollars from a Silicon Valley leader and a chance to live in San Francisco in order to work on the start-up project of their dreams, but they have to quit school first. Duration: 02:20 Video provided by AFP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins