Outer Limits of Reason (27 page)

The first number and the last number sum to 91. The second number and the next-to-last number sum to 85. These two sums are not the same but they are close enough. Continuing in the same way gets us numbers in the same ballpark. What this approximation algorithm does is send each of these similar sums to different partitions. It might not be the best solution, but it is better than waiting for 400 trillion centuries.

 

Every time a new NP-Complete problem is found, there is a search for good approximation algorithms to help solve the problem. As we said, NP problems arise all over and are important. Industry must find a way to deal with such problems. Approximation algorithms are not only formulated and described but are also compared with each other and analyzed. Which heuristic is better? Which algorithm gets you closer to the unobtainable real answer? Which algorithm works faster? Which of the algorithms gets the correct answer for more of the inputs? There is much work to be done.

5.5  Even Harder Problems

NP
is not the end of the story. There are problems that demand even more operations than 2
ⁿ
and
n
!. There are some (not-so-easy-to-describe) problems that require

operations called
superexponential problems
. Rather than spending time discussing such problems, let us look at how large this function is. For a small input of size
n
=
10, the exponential is 2
¹⁰
= 1,024. Using 1,024 as an exponent, we have
2
¹⁰²⁴
,
which is larger than any imaginable number.

There are similar crazy functions like

(
n
!)! or 2
^n
!
.

Try plugging in some small values for
n.

Until now, we have focused on how many operations a computer needs to perform in order to solve a problem. The number of operations is proportional to the amount of time needed to solve the problem. However, there are other ways of measuring how difficult problems are. Harder problems not only demand a lot of time but also a lot of memory space to solve. When a computer solves a problem, it uses memory to store some calculations. The more space needed to store calculations, the harder the problem is.

As before, every algorithm has a function associated with it that describes how much memory space is needed in order to solve the problem. The larger the function, the more space is needed and the harder the problem.

An interesting class of problems consists of those that demand a polynomial amount of space. This class is denoted as
PSPACE
. It is known that
NP
, the set of problems that can be solved in exponential or factorial time, can be solved in polynomial space. In other words,
NP
is a subset of
PSPACE
.

There are many examples of problems that are in
PSPACE
, and some of them have to do with games. There are games with two players that have winning strategies—that is, there are surefire ways for one particular player to win the game. Consider the game of tic-tac-toe. It is known that the first player has a strategy to either force a draw or a win. Now consider a generalization of tic-tac-toe, which, rather than dealing with a three-by-three grid, deals with an
n
-by-
n
grid. Is there a winning strategy for one of the players in this game? The answer might depend on
n
. Determining whether there is a winning strategy for a given
n
-by-
n
game is a problem in
PSPACE
. Other types of generalized games like chess, checkers, connect-four, nim, go, and others are also known to be in
PSPACE
.

In conclusion, there are many different types of computer problems, ranging from easy to very hard. These classes of problems can be envisioned as in
figure 5.18
.

This diagram is a small part of a larger picture that we will meet in the next chapter when we encounter problems that cannot be solved in
any
amount of time and space.

Further Reading

Section 5.1

A popular history of algorithms can be found in Berlinski 2001. Harel 2003 is a popular text that covers everything done in this chapter. Pages 100–107 of Barrow 1999 also cover some of the same topics. There are many wonderful textbooks on algorithms; Baase 1988, Corman et al. 2002, and Dasgupta, Papadimitriou, and Vazirani 2006 are just a few.

The history and significance of the Königsberg Bridge Problem are discussed on pages 364–365 of Eves 1976 and on page 232 of Ross and Wright 2003. Ross and Wright is also a good place to learn more about basic graph theory.

For a more abstract view of algorithms and an exact definition, see Yanofsky 2011.

Section 5.2

All five of the NP problems can be found in Baase 1988, Corman et al. 2002, and chapter 9 of Papadimitriou 1994.

Section 5.3

For a general discussion of NP-Completeness see Garey and Johnson (1979), which remains an excellent book. The second half of the book lists over 300 NP-Complete problems. For a popular account, see chapter 9 of Poundstone 1989.

A nice short presentation of many different classes of problems and their relationship with each other can be found in
chapter 8
of Yanofsky and Mannucci 2008. That wonderful textbook is also where you can learn a lot more on quantum computers and why they will not really help with NP problems.

The Cook-Levin theorem can be found in their original papers: Cook 1971 and Levin 1973. There is a very readable account with technical details in section 2.6 of Garey and Johnson 1979. There is also a more intuitive account that is closer to our presentation in section 34.3 of Corman et al. 2002. Stephen Cook, one of the founders of the field and one of the first to formulate the
P
=?
NP
question, wrote a very nice, readable paper introducing the problem. He also discusses some related results and explains why this problem is so important. This is one of the seven articles presenting the Millennium Problems of the Clay Institute.

Section 5.4

Approximation algorithms can be found in section 9.3 of Baase 1988, chapter 35 of Corman et al. 2002, chapter 6 of Garey and Johnson 1979, chapter 5 of Harel 2003, chapter 9 of Dasgupta 2006, and chapter 13 of Papadimitriou 1994.

Section 5.5

For more information about what is beyond
NP,
see chapter 6 of Garey and Johnson 1979, the end of chapter 3 of Harel 2003, and part V of Papadimitriou 1994.

6

Computing Impossibilities

I whispered, “I am too young,”

And then, “I am old enough”;

Wherefore I threw a penny

To find out if I might love.

“Go and love, go and love, young man,

If the lady be young and fair.”

Ah, penny, brown penny, brown penny,

I am looped in the loops of her hair.

O love is the crooked thing,

There is nobody wise enough

To find out all that is in it,

For he would be thinking of love

Till the stars had run away

And the shadows eaten the moon.

Ah, penny, brown penny, brown penny,

One cannot begin it too soon.

—William Butler Yeats (1865–1939), “Brown Penny”

The only way of finding the limits of the possible is by going beyond them into the impossible.

—Arthur C. Clarke (1917–2008)

In the end, we self-perceiving, self-inventing, locked-in mirages are little miracles of self-reference.

—Douglas R. Hofstadter,
I Am a Strange Loop

Computers can do many wonderful things. However, there are many tasks that they cannot perform. Computers cannot determine whether a painting is beautiful; they do not “understand” moral issues; and they cannot fall in love. Such “human” processes are beyond computation. Whether a painting is beautiful is subject to taste, and computers don't have taste. They also don't have a sense of ethics to deal with moral questions. All of these questions are subjective and computers don't do well with subjective questions. In this chapter, we will explore certain problems that have objective answers but that nevertheless cannot be solved by computers.

It is important to note that these tasks do not require a long time to compute (as in the last chapter); rather, they can
never
be done. Nor is this a problem related to our current level of computer technology. No computer, regardless of how fast and powerful, will ever be able to solve these problems.

Section 6.1
starts with a short discussion of programs, algorithms, and computers. A problem that cannot be solved by any computer, the
Halting Problem
, is introduced in
section 6.2
. I show that it is not solvable by any computer. This is not to be taken on faith. Rather, I carefully go through the proof that demonstrates any computer's inability to solve this problem. With the unsolvability of the Halting Problem in hand, I move on to
section 6.3
, where I show that many other problems are unsolvable.
Section 6.4
describes a hierarchy or classification of unsolvable problems. I conclude with
section 6.5
, which addresses more philosophical questions like the relationship of brains, minds, and computers.

6.1  Algorithms, Computers, Machines, and Programs

We have all experienced computers “getting stuck” or entering into an “infinite loop.” Try as we like, our computers get looped in the loops of their programs. Once in an infinite loop, they never leave. Microsoft Windows taunts us with the words “Not Responding.”
¹
Wouldn't it be nice to buy a piece of software with the reassurance that this could never happen? It would be great if there were some method to determine if a program will halt (or terminate) in a normal manner as opposed to entering into an infinite loop. Alas, no such method exists. This is one of the first problems shown to be unsolvable by a computer. Even though the question of whether a program will halt is objective and not subjective, there is no way a computer can solve it.

Before we begin, some terminology is in order. A
computer
is a physical
machine
that executes
algorithms
.
Programs
are exact descriptions of algorithms. When we say that there is no algorithm that solves a particular problem, we also mean that there is no program, computer, or machine that can perform that task. We are describing a limitation of mechanized processes and we will employ all four of these words interchangeably.

In my discussion of whether a program does or does not halt, rather than talking about all programs, I restrict myself to special types of programs that only deal with whole numbers. Before suspecting that I am trying to trick you by only looking at this restricted set of programs, you should keep two things in mind. First, I am going to show that even for this restricted set of programs, no computer will be able to determine if such programs halt or not. Certainly no computer will be able to determine this for
all
programs. Second, programs that deal with real numbers, graphics, robotics, and all the amazing machines that computers operate, can work by manipulating whole numbers. Such numbers encode different types of more complicated numbers and objects. So if we are going to show a limitation on programs that only deal with whole numbers, there will certainly be limitations on the more complicated types of programs.

The programs I work with are readable by anyone. No programming experience is needed. One simply analyzes the programs from the top down. There are different variables, like
x
,
y
, or
z
, which hold whole numbers. The statements in the programs are obvious. For example, there might be

x=y+1
.

This means that the variable
x
is assigned the same value as
y
with 1 added to it. We can also do something like

x=x+1
.