To be or not with PCP

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

A set of problems,
Intractable or easy?
We may never know.


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


Exponential time --
takes too long to solve 3-SAT.
Answer: PCP.

Random 3-SAT guess
is 7/8-accurate.
More is NP-hard.


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


3SAT is NP-complete,
say complexity theory elite.
But watch PCP -
It covers NP,
and randomized checkers are sweet.


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.


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