Conversations with Bill

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?

BILL: No.

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?

DARLING: Right.

BILL: And I could say that I could construct such sets by diagonalization, but you want a natural set, right?

DARLING: 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.