"Identify something that you liked in COS 487  (Theory of Computation) in F'00. Express your thoughts in prose or verse."

Excerpts from the class's responses:


Amy Wang


All NP problems
Will be solvable in P
If P is NP

Ask an oracle,
How many TMs will halt,
Then, wait and see which.


Yaoping Ruan

Here comes digital security
Two large primes (multiplied).
No one knows them
Except you and God.

Dwight Rodgers

Reliability, scalability, efficiency --we want all these services...
We want compilers to produce the optimal code; we want the
optimal register colorings. We want P=NP. .. We want the Halting problem to be decidable...

Alex Reznik

Of Goedel, laughing, did I dream
Who stated with delirium:
P isn't NP, this is a Truth,
But alas, not a Theorem.


Xinming Ou

I never imagined that taking a random walk in a graph can be of
any help to finding a path between two nodes in it..


Peter Richter

Take a math system..
A most surprising result:
Some truth has no proof.

Kevin Chang

Perhaps the coolest, most unbelievable thing I learnt in class was
the equivalence of the billiard ball setup and the Turing Machine.
How bouncing pool balls around and shooting them into one pocket could possibly compute anything is beyond my imagination.

Krysta Svore

Caesar encoded messages for protection
Rivest used modular exponentiation
Yet seemingly secure communication
...exists not even for a theoretician...

Jared Kramer (in the style of "The Waste Land")

Of what use is a Pushdown Automaton? I know of no living adventurer who has claimed to see a nondeterministic

creature with a stack of infinite capacity...

How to make a Hamiltonian Path out of a boolean formula. I wanted to know how to make a subset sum problem

out of a boolean formula...

Ruoming Pang

...in the eyes of "God," everything is deterministic (if God exists and determines everything), while a human, unable to understand precisely what happens in the world (as Physics shows, there are   limitations on how humans can understand the world), can only handle this unpredictability with a probability model: that's what we call "randomness."

James Percy

It would be incredibly difficult and mind boggling to think about the computation histories or configurations of a modern PC...with gigabytes of memory, we quickly approach a state size bigger than we could ever use in all of our lifetimes put together. ...(Yet) we could, in theory, detect if our machine is caught in a loop..

Julia Salzman

CS487 has begun to make me wonder whether the theory of computation is approaching its boundaries of constructive observation, particularly its ability to prove some of the hierarchy conjectures. When does a theoretical framework exhaust its ability to give constructive and innovative insights into human intellectual ability?

Nitin Garg

..makes me wonder if a human being is ultimately one giant Turing machine. If so, one day it should be possible for us to get a complete description of ourselves and then simulate ourselves!...

Hangsheng Wang

..because modern computers are unsuccessful in emulating human intelligence, I do believe there exists a kind of computation model that is more powerful than a Turing machine...

Jia Xu

The more you learn, the more puzzled you are. Something decidable, but we cannot give a direct answer to it, such as whether God exists. Something intuitively obvious, but we..have no proof, such as NP ?= P...

Junwen Lai

Several sets of problems
We know they are difficult
But even more confusing:
Which set is bigger?

Wen Xu

..how to measure parallel complexity? ...Systems people always argue whether message passing or shared variables is better. If we could find a lowerbound, they could stop this arguing...

Andy Bavier

My imagination was fired by the relationship between P and NP.
It seems amazing on the surface that such an important question
has not been resolved. The million dollar prize may have encouraged my interest too...