Pug’s Place

You know you want to. Go on. I’ve seen your dreams. I’ve analyzed them in high-order polynomial time, and you better believe we’re talking big-theta notation here. So do it, step into this dusty road between these ramshackle saloons and late-model riding Lampropeltis getuluses, look into my eyes, steady your nerves and reach for your quizzing sticks. I dare you, you cur. I double-dog dare you.

Before your blood runs into the sand I should tell you that I’m not the kid you saw out here earlier. I’ve done a lot of growing up since the last time we faced each other in this street. This is an NP-hard world and I’ve adapted. I have a clear mind and I know, I know that everything boils down to black or white, true or false. The world is NP-hard and I can reduce it all to a string of ya’s and no’s. In polynomial time, no more, no less. Cook? I know what he knows. Afraid yet? You should be. ∑_i=0…∞x_ip_i. That’s right, I’m looking for trouble.

Oh, ohh. A big man, making a P with your fingers. Yeah, I can’t prove P=NP, and nor can you, so shut yer mouth. And yer fingers. Give me a certificate and an NP problem and I’ll validate it for ya, fast. Try it. Or are you scared? Ha! Reducing the Hamiltonian Circuit problem to the Hamiltonian Path problem is easy. Can you do it? It’s possible in O(n²) time, and I can. You show me an NP-complete problem, I’ll show you it lies on the intersection of NP and NP-hard. You tell me an NP-hard problem and I’ll ask “to what other NP-hard problem should I reduce it?”

I’ll cover your vertices, I’ll find your subset sums, I’ll color your nodes, hell - I’ll even reduce those problems to the Windows Minesweeper Consistency Problem.

Not so confident anymore, are ya, boy?

I ain’t backing out, and I know you ain’t either. I’ll meet you out here Wednesday at teatime and we’ll finish this.