NP != P

TTTO “אני רואה אותה בדרך לגימנסייה” by Arik Einstein

I have a problem here, solutions take forever
Some cities need me to be there, ASAP
And since I have no time and flying is not free
I wish to minimize the path on which I’ll be

I cannot contemplate quite how to solve this problem
But there’s another, and I think you will agree
That if I solve it polynomially — in time P
Then the last one will a problem cease to be

Can anyone here help me solve
I knew you’d hate to be involved

For there’s a formula, of true and false — that’s logic
And it’s an and of ors and each or is of three
I need to know whether I can it satisfy, see
I need to know if a solution is it be

Can anyone here please help me
How come when I ask, people flee

I have a problem here, solutions take forever
And now I fear that a solution there won’t be

Advertisements

1 Comment

  1. Filk roundup: more and stranger « Moshe’z said,

    […] roundup: more and stranger NP!=P is a song I wrote about NP problems after realizing I need to do an Arik Einstein parody. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: