Researchers have developed tools to solve many so-called intractable computer problems, at least in certain practical situations, by using methods that avoid searching the lengthy paths that occur in “heavy tails” of a path distribution.

One of the most effective approaches is to find a “backdoor set” — a small number of key variables whose values can be fixed in advance. In an airline scheduling problem with 10,000 variables, for example, sometimes fixing just 12 of them ahead of time makes the problem easy.

Cornell University news release