Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!think.com!sdd.hp.com!zaphod.mps.ohio-state.edu!magnus.ircc.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!WISDOM.WEIZMANN.AC.IL!harel
From: harel@WISDOM.WEIZMANN.AC.IL (David Harel)
Newsgroups: comp.theory
Subject: dreams...
Message-ID: <9102191402.AA08433@hadar.wisdom.weizmann.ac.il>
Date: 20 Feb 91 21:38:24 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: David Harel <harel%wisdom.weizmann.ac.il@VM1.NoDak.EDU>
Lines: 33

"I have a dream ..."
	   (Martin Luther King)

I thought it would be nice to share with you a dream I had last
night. (Some people dream a lot; I don't. Some probably dream about
their work; I have never.)

The dream featured Roger Penrose, who had just proved that P=NP.
He kept saying that he had done some work on approximate solutions
to the timetable problem (or the traveling salesman problem -- I can't
remember which one it was), and, in thinking them over a few days ago,
a polynomial-time solution suddenly came to him.

All dreams seem to have a frustrating part to them, and this was no
exception. There were two. One was my repeated, frantic attempts to
try to get Penrose to explain the solution to me. No luck! What a pity.
Try to imagine a story in the New York Times science section, describing
the solution to the P vs. NP problem as having been revealed to the
author in a dream...

The other frustration, involved trying to convince all kinds of strange
people who kept showing up in my office at all hours, demanding that I
explain what more is there to complexity theory, and what will all the
great talents in this area do, now that not only has their main open
problem been resolved, but it has been resolved in such a way as to
render equivalent so many interestingly different-looking complexity
classes. I remember having only very feeble and unconvincing answers
for them, and kept mumbling all kinds of junk...

That's when the dream ended. No, there was no screaming or cold sweat
or anything like that, but I sure hope P is not equal to NP.

David Harel