Wednesday, October 20, 2004

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?


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.


  1. Wow, these are the only conversations with Bill I have experienced or heard about where Bill didn't call someone an idiot.

  2. Wow! This is the first conversation I've read about, heard about, or heard, where Bill did not call someone an idiot (or worse).

  3. Are "proofs" in CompSci as rigorous as those in Mathematics?

  4. Does MOM also have trouble understanding the traveling salesman problem? Maybe it's easier to think abstractly about *a* set of cities than *the* (?) set of states. Though you might want to call it "traveling salesperson."

  5. Naturality of the problem is like a LOGSPACE reduction.
    1 there must be a short and easily understandable description of the problem in the terms tought in basic computer science/discrete mathematics course
    2 the problem description must be short
    For example, a tiling problem is natural. Everybody knows about tiles, squares, and can understand that this one is a good palcement of tiles and this one is bad.
    REgexp with squaring seems to be good, but not SO natural because of squaring which is quite 'unnatural'. It is too different from other operators.
    For example, unsatisfiability of FOL (clearly known by every undergraduate) over reals is also "natural"

  6. sorry, I have lost a part of a sentence
    I meant reals with addintion and linear order (by Berman)

  7. Maybe Bill stopped calling people idiots because he jumped on the theory bandwagon and became "too nice?"