P and NP madness


The problem is hard
As hard as it may be
To decide in a time
Polynomially

If P and NP
In the same clique
Can easily solve
The problem CLIQUE

There is an answer
For this problem hard
Solve using SAT
If you are smart

Need some tape
A read write head
To build a machine
Turing instead

Cook and Levin
Came in to action
To give a break
Overwhelming madness

If we prove
Using reduction
Thus they found
NP-Completeness

Rusiru Boteju

Advertisements

3 thoughts on “P and NP madness

  1. Dude now i think the link between the second and third verse is a little wrong. 3SAT is polynomial time reducible to CLIQUE. So you solve clique u solve 3SAT. :S

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