要是理论计算机教材都能写的这么有趣就好了…

When a P-man loves an NP-woman

Haipeng Guo

Been a happy deterministic man
With a simple polynomial brain
I contented myself with P problems,
And always looked at NP with disdain.

Fell in love with a polynomial woman,
But with a non-deterministic wit,
She said she would marry me,
Only if I could show her that P=NP.

I rushed to the library and studied,
Asked Garey & Johnson for a hint to the truth,
They said "this is quite a hard question",
But none of them had a hint or a clue.

Went to church and prayed to The Almighty,
"Please Oh Lord, give me a lead the truth",
"Don’t waste your time son", a voice said laughing,
For I myself on this wasted my youth.

First oracle says you will marry
Second one tells you you’ll split
Time moves, paths branch, results may vary
Accept the state that finally fits

If you finally marry this girl,
And P=NP was true,
What a Chaos: E-banking unsafe, Salesmen traveling cheaply!
And mathematicians with nothing to do!

If I grant your happiness,
The precondition must be no witness,
Even you both did nothing completely wrong,
The punishments will be exponentially long.

If you really want to marry this woman,
Then randomness might be the only key,
But please stop praying for an answer to me,
For I could not decide on this P=NP!

当P男子爱上NP女子

我是个快乐的确定型男子，(P确定性)
有简单的多项式脑子，(P多项式可解)
自我满足于P问题，
一贯蔑视NP。

爱上了一个多项式女子，
可她有非确定型智慧，(不确定多项式可解)
她说肯嫁给我，
条件是我向她证明P=NP。

我冲进图书馆里研究，
问Garey和Johnson关于真相的暗示，
他们说：“这可真是个难题”，
两人也都没有暗示或线索。 (Garey&Johnson: computers&intractability, 经典参考书)

又来到教堂向全能者祷告：(双关：Alonzo Church, 图灵和kleene的导师, church-turing thesis)
“主啊，求你，带我到真相那儿吧”。
一个声音笑着说：“孩子，不要浪费时间了”，
我已经把青春浪费在这上面了。

第一个神谕说：你们将结合，(P^A = NP^A, oracle machine,一种图灵机)
第二个神谕说：你们将分离。(P^B not= NP^B)
时光流逝，路径分岔，结果可能变化， 
接受最终的结局吧。 (自动机理论)

假如你最终娶到这个姑娘，
P=NP是真的，
多大的一场混乱啊：电子银行不安全，推销员不费力气满天飞！
数学家通通失业！(e-banking, 推销员都涉及经典NP问题)

要我准许你们的幸福，
前提是必须没有见证人，(NP-witness)
即使你们俩都没有犯大错，
这代价也将是指数那样长。(NP is in EXP)

如果你真想娶这个女子，
随机性可能是唯一的钥匙，(NP=PCP(log,1))
请停止向我祷告以求答案，
连我也不能决定是否P=NP