"Charles Stross - Antibodies" - читать интересную книгу автора (Stross Charles)

mathematics: that certain operations are inherently more difficult than others. For
example, finding the common prime factors of a long number which is a product of
those primes is far harder than taking two primes and multiplying them together.

Some processes are not simply made difficult, but impossible because of this
asymmetry; it's not feasible to come up with a deterministic answer to certain puzzles
in finite time. Take the travelling salesman problem, for example. A salesman has to
visit a whole slew of cities which are connected to their neighbours by a road
network. Is there a way for the salesman to figure out a best-possible route that visits
each city without wasting time by returning to a previously visited site, for all
possible networks of cities? The conventional answer is no тАФ and this has big
implications for a huge set of computing applications. Network topology, expert
systemsтАФthe traditional tool of the Al communityтАФfinancial systems, and ...

Me and my people.

****

Back in the QA lab, Amin was looking decidedly thoughtful.

"What do you know?" I asked.

He shook the photocopy at me. "Looks good," he said. "I don't understand it all,
but it's at least credible."

"How does it work?"

He shrugged. "It's a topological transform. You know how most np-incomplete
problems, like the travelling salesman problem, are basically equivalent? And they're
all graph-traversal issues. How to figure out the correct order to carry out a
sequence of operations, or how to visit each node in a graph in the correct order.
Anyway, this paper's about a method of reducing such problems to a much simpler
form. He's using a new theorem in graph theory that I sort of heard about last year
but didn't pay much attention to, so I'm not totally clear on all the details. But if this
is for real..."

"Pretty heavy?"

He grinned. "You're going to have to re-write the route discovery code. Never mind,
it'll run a bit faster ..."

****

I rose out of cubicle hell in a daze, blinking in the cloud-filtered daylight. Eight years
lay in ruins behind me, tattered and bleeding bodies scattered in the wreckage. I
walked to the landscaped car park: on the other side of the world, urban renewal
police with M16s beat the crap out of dissident organizers, finally necklacing them in
the damp, humid night.

War raged on three fronts, spaced out around a burning planet. Even so, this was by