Here are some poems referring to the last lectures of CS270 which

discussed the (non)approximability of 3-SAT to better than 7/8,

probabilistically checkable proofs, np-completeness, and the linearity

testing based proof of pcp=np.

-------------------------------------

My name: Nemanja Isailovic

Haiku

A set of problems,

Intractable or easy?

We may never know.

Limericks

There once were a tough set of problems;

Many theorists tried hard to solve 'em.

But all they e'er say

Was, "Just give me a way

To solve one and I'll have solved all of 'em."

One clever young theorist said, "Gee!

I'll define a new type called PCP."

So he did some contemplation,

Spent many days on calculation,

And finally said, "Damn, it's no simpler than NP!"

------------------------------------------

Andrew Zimdars

Tuesday:

Exponential time --

takes too long to solve 3-SAT.

Answer: PCP.

Random 3-SAT guess

is 7/8-accurate.

More is NP-hard.

Thursday:

When the table lies

you can see that the numbers

don't describe a line.

Verified answers:

linear and consistent

vector expressions.

Verifier checks

parity in lieu of truth

to root out falsehood.

And a meta-summary:

Summary haikus

make it hard to capture proofs

with lots of symbols.

--------------------

Dennis Geels

Tuesday:

3SAT is NP-complete,

say complexity theory elite.

But watch PCP -

It covers NP,

and randomized checkers are sweet.

Thursday:

We randomly sample the proof

but aren't so easy to spoof.

Just make the proof bigger,

and somehow we figure

The storage won't go through the roof.

Final:

This class will live on

in the minds of us students.

In Theory, at least.

------------------------------------

From Mark Piloff

The muses paid me a visit tonight, but when I told them I wanted to write a

poem about Complexity Theory they told me I was on my own for that one. So

here it is, devoid of any literary merit but hopefully amusing nonetheless.

Ode to CS270

Twas the second day of May, the next to last day of class

We sat pondering the final, and hoped we might pass.

The door flew wide open and then proclaimed Satish:

I’ve got complexity theory that I must unleash!”

NP was defined and Cook’s theorem was stated:

“If you can solve 3SAT, this whole field’s antiquated.”

And though it’s a worthy pursuit, showing P = NP,

I think I’ll leave that task to someone smarter than me.

But an approximate solution! Wouldn’t that be great?

You can’t win them all, but how about seven of eight?

This proved to be easy, we’ve got this one wired:

Conditionally assign, and negate if required.

But theorists are greedy-- I’m a 3SAT whore,

Surely it’s no trouble to satisfy a few clauses more

In pursuit of this goal, PCP was defined.

(And I don’t mean the drug, though it’s just as harsh on the mind.)

From PCP we proceed with some clever deduction

and return to > 7/8 3-SAT via complexity reduction.

So what’s the big deal? What course have we charted?

Turns out PCP = NP and we’re back where we started.

-----------------------------------

3-SAT is hard but

complexity theory's worse.

Randomness can help.

:)

Sean Rhea

---------------------------------------

Curses, no time for rhymes.

--Chris Wells

---------------------------------------

:-) Since a poetic summary of the last two lectures (or perhaps the class

in general) is apparently called for, here's my take at it. Unlike the

literary masters among us, I'll modify old poetry rather than creating my

own. You should consider colecting all of the class creations and sending

them back out to the mailing list. :-)

- Wes

I know a proof you do not know,

Which says they are the same,

So I'll show you a simple proof,

Which will the former frame.

-CS 270, PCP and NP

I hear a voice you cannot hear,

Which says I must not stay;

I see a hand you cannot see,

Which beckons me away.

-Thomas Tickell, Colin and Lucy

Through life's vast ocean of algorithms we sail

'Deterministic' the card, but 'Randomized' the gale.

-CS 270, Summary Essays

On life's vast ocean diversely we sail,

Reason the card, but Passion is the gale.

-Pope, Moral Essays, I

Complexity Theorists are the hierophants of

an incomprehensible inspiration;

the mirrors of the gigantic classes

which analysis casts on computation.

-CS 270, A Defense of Complexity

Poets are the hierophants of

an unapprehended inspiration;

the mirrors of the gigantic shadows

which futurity casts upon the present.

-Percy Bysshe Shelley, A Defense of Poetry

I cannot see the whole proof, and so I must wonder:

Illumine only three bits, or some linear forms,

What tricks can an adversary play?

-CS 270, The Drunken PCP Verifier

I have seen the sunset, stained with mystic wonders,

Illumine the rolling waves with long purple forms,

Like actors in ancient plays.

-Arthur Rimbaud, Le Bateau Ivre

To know

Which problems before us lie in PCP,

Is the main theorem; what is more is fume.

-CS 270, 3SAT Approximations Lost, VII/VIII

To know

That which before us lies in daily life,

Is the prime wisdom; what is more is fume.

-Milton, Paradise Lost, VIII

Long, long be my head with such proofs fill'd!

Like the textbook in which great thoughts have one been distill'd:

You may burn, you may tear up the book if you will,

But the gist of the methods will hang round it still.

-CS 270, Farwell! But CLR...

Long, long be my heart with such memories fill'd!

Like the vase in which roses have once been distill'd:

You may break, you may shatter the vase if you will,

But the scent of the roses will hang round it still.

-Thomas Moore, Farewell! But Whenever...

Why do two complexity classes, put one next to the other, equate?

Can he really explain this? no.

Just as we can never seem to learn big-oh notation.

-CS 270, Artful Exam Mistakes

Why do two colors, put one next to the other, sing?

Can one really explain this? no.

Just as one can never learn how to paint.

-Pablo Picasso, Arts de France

A proof that's told with good intent

Is more confusing than you meant!

-CS 270

A truth that's told with bad intent

Beats all the lies you can invent.

-- William Blake

Ah, but a man's conjectures should exceed his proofs,

Or what's his PhD for?

-CS 270, "Satish Rao"

Ah, but a man's grasp should exceed his reach,

Or what's a heaven for?

-- Robert Browning, "Andrea del Sarto"

Between the idea

And the class

Between the whiteboard

And our eyes

Falls his Shadow

-CS 270, "The Intervening Man" (sorry, you sometimes block the board)

Between the idea

And the reality

Between the motion

And the act

Falls the Shadow

-- T.S. Eliot, "The Hollow Man"

But theorists, who ought to know

Assure us that it can't be so.

Oh, let us never, never doubt

What nobody is sure about.

-CS 270, P==NP

But scientists, who ought to know

Assure us that it must be so.

Oh, let us never, never doubt

What nobody is sure about.

-- Hilaire Belloc

Bits in your multitudes

Scarce to be counted

We need but sample

A few random ones.

-CS 270, "Bits"

Stars in your multitudes

Scarce to be counted

Filling the darkness

With order and light.

-Les Miserables, "Stars"

----------------------------------------------------------------

Tuesday's lecture:

Try it once:

It isn’t at all hard to say

What we covered in class today

Just flip a coin, and then sit tight

While we check to see if it is right

But the math gods are not playing fair

Your clever tricks get you no where

The same old curse, they do repeat

It’s doomed to be NP- complete.

Then try again:

It’s really hard, I do repeat.

It is what they call NP-complete.

No, no, at last we will be free,

I got a scheme called PCP.

I know that you will quickly see,

this problem is not NP, just P.

Alas, you say, you don’t agree?

It’s really hard, I must repeat.

You can’t escape NP-complete.

Carol Hurwitz

-----------------