When a P-man loves an NP-woman
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!
两人也都没有暗示或线索。 (Garey&Johnson: computers&intractability, 经典参考书)
又来到教堂向全能者祷告：(双关：Alonzo Church, 图灵和kleene的导师, church-turing thesis)
第一个神谕说：你们将结合，(P^A = NP^A, oracle machine,一种图灵机)
第二个神谕说：你们将分离。(P^B not= NP^B)
这代价也将是指数那样长。(NP is in EXP)