(Haiku)

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.

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

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

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

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

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

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.

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

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

...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."

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

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?

..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!...

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

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

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

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

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