An Oracle for NP

Posted on December 13, 2005 by Jenna

← Previous | Next →

“The nuclear device is going to go off in less than four hours,” says Brad.

“And we don’t even have a suspect,” sighs Steve.

They look gloomily at the dingy gray wall of their lab.

“Would it help? I mean, at this point?” Brad says.

“We could torture them,” says Steve. “And find out where the device is. Then we could evacuate people and save thousands of lives.”

“Point,” says Brad.

Both of them sigh.

“What if we torture you?” Brad asks.


“Well, it’s doing something,” Brad points out. “I mean, at least it’s not just sitting here.”

“I can see how you might feel that that might be necessary,” Steve says.

He doesn’t mean that. He’s actually retreating, just a tiny bit, while watching Brad very carefully for indications that Brad is kidding.

Unfortunately for Steve, he isn’t.

“Gya!” screams Steve, not much later. Then he babbles. Then he begins to talk. “I’ll tell! I’ll tell you anything!”

“Where’s the nuclear device?” Brad demands.

“It’s at 1010 Rue de la Forge!”

Steve pauses. He blinks. Even through the mist of pain, he’s surprised by the fact that he said that.

“I’ll send someone to check that out,” says Brad, darkly, threateningly. He does.

“It’s the truth,” says Steve. “I don’t know how I knew. But it’s the truth.”

A few minutes pass. Brad’s phone rings. He listens to it. He hangs up. Then he stares at Steve in growing wonder.

“It was there.”

“It was there?”

“It was there.

Brad shakes his head.

“Wow,” Brad says. “It must be the torture.”

“Let me try!” says Steve. He flails his shackled arms.

“Not on me!” says Brad, looking a little ill.

“Maybe on Helen?”

Experimentally, they torture Helen. “Surely, you’re familiar with Godel’s subversive theorem,” Steve interrogates. “But can you actually give a statement that’s true but unprovable within the logical framework in which we live our lives?”

“This one!” wails Helen.

Steve frowns. “Hey, is that right?” he asks Brad.

“I think so,” says Brad. “But I can’t construct a proof, offhand.”

“Ha!” says Steve.

It makes big news. Defusing nuclear devices in the nick of time always does, and the bit about Godel keeps the story alive in the mathematical journals. Soon everyone understands just what forcibly destroying a person’s mind can do.

“Can you solve an NP-complete problem in polynomial time?” harshes Associate Professor Kazer, the official torturer of the Stanford Computer Science Department.

Amelia, his best graduate student, whimpers.

“Please,” she says. “Make it stop!”

Can you?

“Yes!” she snaps.

“Give me a constructive proof!”

And she does.

It is a wave of change. Suddenly from the National Center for Public Policy issue bold new programs; and everyone who reads their reports finds themselves marveling at the simplicity and clarity of each torture victim’s thoughts.

The Fed no longer relies on archaic pre-torture economic theory. Screams point their way to the perfect rate.

The nation prospers as never before. Great towers rise. Flying cars are everywhere, fueled not by oil but by ordinary kitchen water.

And in Brad’s lab (for it is no longer considered appropriate for such people as Steve and Helen to be considered his equals), Brad whispers gently to Steve, “How can I make such pain unnecessary?”

“You can’t,” says Steve.

“I can’t? Why not?”

And there is a whimpering and a shout from Steve that subsides quietly into sobbing and to words.

“The data is the suffering,” answers Steve.