When a P-man loves an NP-woman
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!