A guest post from William Gasarch
Why is it hard for us to explain to the layperson what
we do? The following true story is telling.
I will label the characters MOM and BILL.
MOM: What kind of thing do you work on?
BILL: (thinking: got to give an easy example)
Lets say you have n, er 1000 numbers.
You want to find the — (cut off)
MOM: Where did they come from?
BILL: Oh. Lets say you have 50 numbers, the populations
of all of the states of America, and you want to find — (cut off)
MOM: Did you include the District of Columbia?
MOM: Why not?
BILL: Because its not a state. But for the example it doesn't matter
because — (cut off)
MOM: But they should be a state. They have been oppressed to long and
if they had their own state then — (cut off)
BILL: But none of that is relevant to the problem of finding
the Max of a set of numbers.
MOM: But the problem of Statehood for DC is a more important problem.
BILL: Okay, lets say you have 51 numbers, the populations of
the 50 states and the District of Columbia.
MOM: What about Guam?
BILL: I should have majored in Government and Politics…
To the person on the street the very definition of
a problem is … problematic. Abstraction that we do without
blinking an eye requires a conceptual leap that is hard or
at least unfamiliar to most people.
Even people IN computer science may have a hard time
understand what we are talking about.
Here is another real life story between
two characters who I will call
BILL and DARLING.
DARLING has a Masters Degree in computer Science
with an emphasis on Software Engineering.
DARLING: Bill, can you give me an example of a set that
is provably NOT in P.
BILL: Well, I could say HALT but you want a computable set, right?
BILL: And I could say that I could construct such sets by
diagonalization, but you want a natural set, right?
BILL: And I could say that the set of true statements in
the language WS1S, but you want a natural set.
DARLING: What is WS1S?
BILL: Weak Monadic Second order with one successor, but I think
you agree that if you don't know what it is then it's not natural.
DARLING: Right. So, is there some set that is natural and decidable
that is provably not in P?
BILL: AH, yes, the set of regular expressions with squaring that
equal Σ* is EXPSPACE complete and hence provably not in P.
DARLING: Why is that problem natural?
BILL: Good Question! A problem is natural if it was being worked on
before someone classified it.
DARLING: Okay. What is the first paper this problem appeared in?
BILL: It was in THE EQUIVALENCE PROBLEM FOR REGULAR EXPRESSIONS WITH
SQUARING REQUIRES EXPONENTIAL SPACE by Meyer and Stockmeyer,
From FOCS 1972.
Oh. I guess that proves that its NOT natural.
This story raise the question—what is natural? Do we need that
someone worked on a problem beforehand to make it natural? Is it good
enough that they should have worked on it? Or that they could have?
Logic has the same situation with the Paris-Harrington results of a
result from Ramsey Theory that is not in Peano Arithmetic, but the
first time it was proven was in the same paper that proved it was not
provable in PA.
Incidentally, there are more natural problems that are not in P.
Some games on n by n boards are EXPSPACE or EXPTIME complete and hence
not in P. Would have been a better answer, though it would not have
made as good a story.