Buy F&SF • Read F&SF • Contact F&SF • Advertise In F&SF • Blog • Forum • RSS

Interview: David Erik Nelson on “The Traveling Salesman Solution”

– The title of your story is “The Traveling Salesman Solution.” What’s the traveling salesman problem?

The Traveling Salesman Problem is sort of a math puzzle, generally stated something like: “Given a list of cities he must visit, and knowing the distance between any of these points, what’s the shortest round-trip that hits each city only once?” It seems easy: You just figure out each possible route, measure it, and compare it to the others to find the shortest one. But the thing is, the set of all possible routes grows geometrically: If you have four cities in your sales territory, then there are six possible routes. If you have five cities, then there are 24 possible routes. Ten cities? 362,880 routes. And on up.

Brainteasers like the TSP are part of a class of problems mathematicians call “NP-complete.” Here’s the catch: Any NP-Complete problem can be transformed into any other NP-Complete problem, so if you find a solution to one of them, you’ve found the solution to all of them. The full set of NP-Complete problems includes other brainteaserish things (like sudoku puzzles and Minesweeper), as well as a host of nitty-gritty biological, economic, and comp sci situations.


– So finding a solution to that problem would be great, right?

Ha! Sorta! On the one hand, it would effectively burst the bonds of what we could make computers figure out, slingshotting our understanding of molecular biology, our capacity to design super-efficient circuits, our ability to analyze really complicated social graphs and food webs, and so on.

On the other hand, we actually rely on the functional unsolvability of NP-Complete problems in order to keep our communications secure and maintain the slim modicum of privacy we still enjoy. In the post-industrial world, it would be incredibly chaotic to abruptly have the Traveling Salesman cease to be a Problem.


– One of the things I love about this story is that the protagonist is an Army vet in a wheelchair. It changes the way he interacts with the world, but it doesn’t stop him from saving it. A lot of the details about him are very specific and feel real. Was the character based on someone you know?

I feel like this question is probably about the narrator’s personality, in which case the answer is “not really”–he’s sort of an amalgam of several folks. His perspective on the military and foreign policy is heavily informed by a couple guys I know who served in Afghanistan and Iraq–both of whom, thankfully, completed their service without significant bodily injuries.

But I was at a Whole Foods one time, drinking a coffee, when I noticed this big blue high-clearance dually pickup parked in the handicap space. I was wondering about the jackass who’d go and swipe the handicap space when a legless African-American lady came rolling up to the truck. She hit the keyless, opened the door, grabbed the inside of the door frame, and swung herself in. Then she leaned out, folded her wheelchair in a single motion, and pulled it in after her, where I guess she tucked it into the passenger side. She drove off, and I was left thinking about how we lump everyone in a wheelchair into this single “handicapped” classification, and how that can probably really start to grate on someone who is, in fact, very able-bodied in most senses, she just didn’t have any legs.


– Your story “No Sound of Thunder” was published in the June issue of Asimov’s. You’ve said that the two stories are sort of alternate-reality versions of each other. What are the two realities?

One of these stories fully and unapologetically embraces being a “grown-up” and accepting the necessity of doing violence to prevent greater violence. The other is romantically certain that we can always find a way to dodge around violence and destruction provided we stay nimble and are willing to make ourselves ridiculous, if that’s what it takes.

This answer probably seems a touch cryptic, but I want to be as non-spoilerish as possible!


– “The Traveling Salesman Solution” is dedicated to Ted Chiang, Michael Hoffman, and Matt Weitzel. What’s the connection between those three?

Well, Ted Chiang is a fantastic fiction writer. I especially love his stories “Exhalation” and “72 Letters.” But he also wrote this great essay that appeared in issue #23 of Lady Churchill’s Rosebud Wristlet: “The Problem of the Traveling Salesman.” He concludes the article by challenging someone to write a good TSP story–which is something I’d already spent more than a decade complaining was basically impossible. But right on the heels of reading Ted’s essay I read this article in the New Yorker about a Michigan dentist who was infamous for his very anomalous marathon results, and suddenly a “good math story” seemed happy to just about write itself.

As for the other two, Michael Hoffman is a friend who served in Iraq as an infantry captain and linguist; a lot of the narrator’s feelings about war and the boogie dark come from my conversations with Mike and reading his writing. Matt Weitzel is a young guy, a programmer, who was kind enough to have cookies and coffee with me when I’d first started working on this story. He patiently explained why my initial framing of the Traveling Salesman Solution wasn’t really a solution, but rather “escaping the problem,” a phrase I loved enough to steal. The narrator inherited his incredulity from Matt.


– There is a lot of math in this story.

I was a crappy math student, but I never had a math teacher I didn’t like. Mathematicians are a sorely underserved community.


– Where can readers go to find out more about your writing? is the best place to start. If they’d like to check out my first time portal story–“The New Guys Always Work Overtime,” which just won the Asimov’s Science Fiction Readers’ Award for Short Story–they can get it for free here:


– “The Traveling Salesman Solution” appears in the July/August issue of Fantasy & Science Fiction. It’s available in both print and electronic formats.


Leave a Reply

If this is your first time leaving a comment, your comment may enter the moderation queue. If it doesn't appear right away, don't panic; it should show up once site administrators verify you're not a spambot. After you successfully post a comment, future comments will no longer be moderated.

You must be logged in to post a comment.

Copyright © 2006–2020 The Magazine of Fantasy & Science Fiction • All Rights Reserved Worldwide
Powered by WordPress • Theme based on Whitespace theme by Brian Gardner
If you find any errors, typos or anything else worth mentioning, please send it to

Designed by Rodger Turner and Hosted by:
SF Site spot art