Red Heaven Space Habitat
Hades Orbit
Folsom 4101-B Star System

“Quite a view, isn’t it?” Captain Catherine Blackwood asked. She was sitting with her first officer, Wolfram von Spandau, in a nice restaurant on the top floor of the Hotel Orbital. The hotel was a cylindrical building, twenty stories high, with a transparent, domed ceiling. The interior of the Red Heaven space habitat circled around and high above her. A cylinder a dozen kilometers long and three in diameter, rotating to simulate gravity, Red Heaven was home to one and a half million residents, and was the only settlement in a very lonely solar system.

Wolfram grunted and sipped his drink. “It is, Kapitänin. I have never seen anything like it.” The interior of Red Heaven was divided into six equal-area sections, running down the habitat’s longitudinal axis. Three of the sections were the station’s habitable land area, covered with layers of soil, roads, buildings, and trees. The other three were transparent windows, which allowed sunlight to be reflected in from giant mirrors outside the station. Clouds swirled overhead, looping around the interior of the station.

Red Heaven got its name from Hades, the massive red gas giant it orbited. Circling around Folsom 4101-B at one and a half astronomical units, Hades’ upper atmosphere was rich in hydrogen, helium, and other gasses ships used as reaction mass. Strategically located along a major trade route between the heart of the Concordiat and the Frontier, Red Heaven had been a major transit hub since its construction at the end of the Second Interstellar War, over a hundred standard years prior.

Mazer Broadbent, Catherine’s security officer, seemed a little unsettled by the view. “It certainly makes one feel small,” he said, before popping another stuffed bell pepper into his mouth. Far above them, through one of the habitat’s three expansive windows, the imposing, blood-red mass of Hades was visible, looming over the tiny human settlement like an angry god. A swirling storm, known to locals as The Maw, was clearly visible. Tens of thousands of kilometers in diameter, the storm had been raging since before humankind had ever entered the Folsom 4101-B system, and it showed no signs of slowing down.

It was late afternoon by the habitat’s internal clock, and the restaurant hadn’t yet been hit by its dinner rush. Most of the tables were empty, giving the three spacers some privacy as they talked. Off to the side of the room, in front of a two-meter-tall artificial waterfall, a boxy robot with two articulated arms expertly played a beautiful grand piano. A server robot would occasionally roll up and ask Catherine’s party if they were ready to order, but the spacers declined. They were waiting for their host, and Catherine thought it would be rude to dine without him.

Imagine you’re a math professor. In between teaching, and attending meetings of the curriculum committee, you spend your time on research. What exactly might you be doing? Well, as the old joke says, "if we knew what we were doing, it wouldn't be research."

But let’s say one of your favorite research topics is something called the “Hamiltonian Path Problem”: given a bunch of cities joined by roads, plan a journey that visits each city exactly once¹. This may seem simple, but it's something that mathematicians actually study, with practical applications.

And imagine that one day you find a solution. Not just any solution, but a relatively efficient one that can be computed in (say) n⁴ steps, where n is the number of cities. So to solve the problem for ten cities using your spiffy new algorithm would take a computer ten thousand operations—your cellphone could do this faster than you could press its buttons. For a thousand cities it would take a trillion operations: this would keep a supercomputer busy for a little while, but is still feasible.

What do you do next? Do you:

1. Collect a million dollars and visit a bunch of cities?
2. Change all your passwords and buy dried food and gold bullion?
3. Burn your notes and go into hiding?

The answer could be any of the above.

First, I hear you ask, where do you get that million dollars? That's the easy bit. Back in the year 2000, the Clay Mathematics Institute published a list of seven “Millennium Problems,” problems they considered to be the most difficult and important of the new millennium. They offered a million-dollar prize for each one. Only one of the problems, the Poincaré Conjecture, has been solved so far². If you are the first to solve any of the others, you'll get the million.

One of them has the terse name "P=NP." It's a problem in the complexity of algorithms, and asks whether a class of problems called "P," that we can solve in reasonable time, is the same as "NP," for which we can verify given answers in reasonable time.

What do we mean by "reasonable"? Any problem is easy if the input data are simple enough. As a result, mathematicians measure the difficulty of algorithms by how the time needed to find a solution grows as the size of the data gets large.