Forum
is more than 125 years old. But
with four or more pegs, the optimal solution length is not known
in general. Using more than 2TB
of disk space, we’ve completed
breadth-first searches of the four-peg Towers of Hanoi problem with
up to 22 discs, a problem with
almost 17. 6 trillion states. We’ve
also performed disk-based heuristic
searches of the problem, confirming a 1941 conjecture due to J.S.
Frame and B.M. Stewart about the
optimal solutions to these problems for up to 31 discs.
As another example, the sliding-tile Fifteen Puzzle was by many
accounts as famous in the 1880s as
Rubik’s Cube in the 1980s, as documented by Jerry Slocum and Dic
Sonneveld in their book The 15
Puzzle: How It Drove the World
Crazy. In 2005, using 1.5TB of
disk space, we completed a
breadth-first search of the 4x4 Fifteen Puzzle, with more than 10
trillion states. This verified a result
due to Adrian Brungger et al. that
the most difficult problem
instances take 80 moves to solve.
We then found that the most difficult instance of the 2x8 Fifteen
Puzzle takes 140 moves to solve.
More recently, we considered
the pancake problem whose only
claim to fame is that it is the subject of a technical paper coauthored by Bill Gates (“Bounds
for Sorting By Prefix Traversal” in
1979). In it, we want to sort a
stack of pancakes of different sizes
using a spatula that flips over the
top K pancakes as a group. In
another version of the problem,
one side of each pancake is
burned; in addition to sorting
them by size, we now want all
burned sides face down. Using
3TB of disk storage, we found the
maximum number of moves
needed to solve the 14 and 15
unburned pancake problems and
the 11 and 12 burned pancake
problems. The 15 unburned pancake problem has more than 1. 3
trillion states; the 12 burned pancake problem has almost two trillion states.
In addition to these challenging
toy problems, many of these techniques are applicable to real-world
problems as well. In particular, most
NP-complete problems are combinatorial in nature, and all known
methods for solving them optimally
involve searching large numbers of
states. I agree with Kunkle and
Cooperman that the use of magnetic disk can increase the feasible
size of memory-limited searches by
several orders of magnitude.
RICHARD E. KORF
Los Angeles
Author’s Response:
We thank Korf for his complimentary comment. We have long
admired his own use of disk-based
parallel computation. We look forward to the popularization of the
technology and its increased use in
real-world problems.
DANIEL KUNKLE
GENE COOPERMAN
Boston
NO ROOM FOR WEAK LINKS IN
SECURITY IN DEPTH
Hal Berghel’s “Digital Village” column (Apr. 2008) “Faith-Based
Security” made valid points and
it’s title was somewhat provocative,
but I take issue with its treatment
of “security in depth.” SID has a
simple definition: create a path of
multiple sequential steps where the
sum of the least cost-path represents the optimal effort an attacker
would have to expend to achieve
the target (nefarious) effect.
The key words are “sequential”
and “sum.” In terms of simple
graph theory, SID forces the
attacker to traverse multiple nodes
representing independent compromises at cumulative cost across all
edges (such as in two-factor
authentication). In contrast, a
“chain link” defense is only as
strong as its weakest link because
the attack takes place simultaneously on all nodes, so the compromise of any one of them
compromises the entire defense
(such as in port scanning). In the
case of a physical chain, straining
the chain simultaneously places
sheering load where each link joins
its neighbor. Once the chain
breaks anywhere its ability to
restrain is gone.
Amazing to me is how many
security professionals and managers do not understand the fundamental difference between SID
and the chain-link style of protection. Worse, they may think they
have a SID architecture when in
fact they have only a chain link.
ROBERT J. DUWORS
Bellevue, WA
FORGET WEP; GIVE ME WPA
ENCRYPTION
The discussion and advice in
Alfred Loo’s “The Myths and
Truths of Wireless Security” (Feb.
2008) did nothing to dispel the
myths, even as it introduced some
advice that should not have been
included. For example, being told
that “Users should turn on the
encryption feature in the router”
was misleading, as it indicates that