tag:blogger.com,1999:blog-3722233.post111265664799743887..comments2024-11-14T17:42:16.782-06:00Comments on Computational Complexity: Math Poetry ContestLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-64269623908117854322009-03-29T12:17:00.000-05:002009-03-29T12:17:00.000-05:00this is bases of the first couple of numbers of th...this is bases of the first couple of numbers of the Fibonacci Series.<BR/><BR/><BR/>Arcs <BR/><BR/>are<BR/><BR/>Measured<BR/><BR/>In two ways<BR/><BR/>One is by degrees<BR/><BR/>And the other is by its length<BR/><BR/>Charlie O'Keeffe <BR/>okeeffe141@yahoo.comCharlienoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114151631472183932005-04-22T01:33:00.000-05:002005-04-22T01:33:00.000-05:00I remember when I was at CTY F&M back in the mid-9...I remember when I was at CTY F&M back in the mid-90s, our Contemporary Mathematics class thought we came up with the idea of Aleph-null bottles of beer on the wall... we even put in on our class shirt at the end of the summer ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114076857472773402005-04-21T04:47:00.000-05:002005-04-21T04:47:00.000-05:00This comment has been removed by a blog administrator.Phunicularhttps://www.blogger.com/profile/17391580744667915640noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1113428852854073362005-04-13T16:47:00.000-05:002005-04-13T16:47:00.000-05:00Not exactly a poem per se, but I did recently comp...Not exactly a poem per se, but I did recently compose a rap ditty on an appropriate theme. (full version with hyperlinks is available <A HREF="http://hughanchor.blogspot.com/2005/03/outreach.html" REL="nofollow">here</A>):<BR/><BR/>Smash the polynomial hierarchy!<BR/><BR/>I got the P! I got the NP!<BR/>Yeah, you know me!<BR/>I got coNP! I got BPP!<BR/>Got them all, don't you see...<BR/><BR/>Give me space! Give me logspace<BR/>Gonna take my place, gonna play my ace,<BR/>My AC0, gonna be a hero<BR/>People think I'm so bizarre, see<BR/>Gonna smash the polynomial hierarchy!<BR/><BR/>My warring machine is a Turing machine,<BR/>Recoil in horror y'all when you see my oracle<BR/>And call for your momma, yeah, when you meet my automata<BR/>Don't get mean, and don't you get snarky<BR/>But I smashed the polynomial hierarchy<BR/><BR/>Take any 3SAT, I spit it right back<BR/>Word to my homies all, it's polynomial<BR/>Me always in P-time, committing no crime<BR/>I steal RSA like it was your car keys<BR/>'Cause I smashed the polynomial hierarchy<BR/><BR/>I got the P! It equals NP!<BR/>I ain't on PCP!<BR/>I got RPP, all of NPC!<BR/>Million bucks be comin' to me<BR/><BR/>Stephen Cook better rewrite the book<BR/>C, L and R S attend my classes<BR/>And Michael Sipser can start calling me sir<BR/>Chris Papadimitriou can worship at my feet, yo<BR/>...don't you be calling me Aho, I ain't no ho...<BR/>[repeat to fade]Hughhttps://www.blogger.com/profile/08767952337717767032noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1113411478728028672005-04-13T11:57:00.000-05:002005-04-13T11:57:00.000-05:00*********************************** ...**********************************<BR/>* * <BR/>* When a P-man loves an NP-woman *<BR/>* *<BR/>**********************************<BR/><BR/>Been a happy deterministic man<BR/>With a simple polynomial brain<BR/>I contented myself with P problems,<BR/>And always looked at NP with disdain.<BR/><BR/>Fell in love with a polynomial woman,<BR/>But with a non-deterministic wit,<BR/>She said she would marry me,<BR/>Only if I could show her that P=NP.<BR/><BR/>I rushed to the library and studied,<BR/>Asked Garey & Johnson for a hint to the truth,<BR/>They said "this is quite a hard question",<BR/>But none of them had a hint or a clue.<BR/><BR/>Went to church and prayed to The Almighty,<BR/>"Please Oh Lord, give me a lead the truth",<BR/>"Don't waste your time son", a voice said laughing,<BR/>For I myself on this wasted my youth.<BR/><BR/>First oracle says you will marry<BR/>Second one tells you you'll split<BR/>Time moves, paths branch, results may vary<BR/>Accept the state that finally fits<BR/><BR/>If you finally marry this girl,<BR/>And P=NP was true,<BR/>What a Chaos: E-banking unsafe, Salesmen traveling cheaply!<BR/>And mathematicians with nothing to do!<BR/><BR/>If I grant your happiness,<BR/>The precondition must be no witness,<BR/>Even you both did nothing completely wrong,<BR/>The punishments will be exponentially long.<BR/><BR/>If you really want to marry this woman,<BR/>Then randomness might be the only key,<BR/>But please stop praying for an answer to me,<BR/>For I could not decide on this P=NP!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112799888969106802005-04-06T10:04:00.000-05:002005-04-06T10:04:00.000-05:00I'd like to nominate Harry Mairson for his poetic ...I'd like to nominate Harry Mairson for his poetic "New Proofs of Old Theorems" available from:<BR/><BR/>http://www.cs.brandeis.edu/~mairson/poems/poems.html<BR/><BR/>These "poems" are in the spirit of "Scooping the Loop Snooper".<BR/><BR/>Luca AcetoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112761833583123952005-04-05T23:30:00.000-05:002005-04-05T23:30:00.000-05:00A shameless rewrite:A sudden blow: the zig-zag exp...A shameless rewrite:<BR/><BR/>A sudden blow: the zig-zag expanding still<BR/>Above the staggering graph, her connectivity enhanced<BR/>By the compact likeness, her path caught in its web,<BR/>It holds her helpless degree upon his degree.<BR/><BR/>How can those powered components reduce<BR/>The increased degrees from its greedy push<BR/>And how can the diameter, stretched and compressed,<BR/>But grow beyond logarithmic size?<BR/><BR/>A step in mid-stage engenders there<BR/>The possible erasure of memory, an additive constant<BR/>And L=SL.<BR/> Being so caught up,<BR/>So mastered by the brute random walk<BR/>Did she put on its knowledge with its power<BR/>Before the s-t connection found?<BR/><BR/>- HominAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112719034432174322005-04-05T11:37:00.000-05:002005-04-05T11:37:00.000-05:00One should never forget the master piece Scooping ...One should never forget the master piece Scooping the Loop Snooper to be found at:<BR/><BR/><A HREF="http://www.ncc.up.pt/~rvr/MC02/halting.pdf" REL="nofollow"> http://www.ncc.up.pt/~rvr/MC02/halting.pdf </A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112718710706649472005-04-05T11:31:00.001-05:002005-04-05T11:31:00.001-05:00Try it once:It isn't at all hard to sayWhat we cov...Try it once:<BR/>It isn't at all hard to say<BR/>What we covered in class today<BR/>Just flip a coin, and then sit tight<BR/>While we check to see if it is right<BR/>But the math gods are not playing fair<BR/>Your clever tricks get you no where<BR/>The same old curse, they do repeat<BR/>It's doomed to be NP- complete.<BR/><BR/>Then try again:<BR/>It's really hard, I do repeat.<BR/>It is what they call NP-complete.<BR/><BR/>No, no, at last we will be free,<BR/>I got a scheme called PCP.<BR/>I know that you will quickly see,<BR/>this problem is not NP, just P.<BR/>Alas, you say, you don't agree?<BR/><BR/>It's really hard, I must repeat.<BR/>You can't escape NP-complete.<BR/><BR/>Carol HurwitzGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112718680712270032005-04-05T11:31:00.000-05:002005-04-05T11:31:00.000-05:00Twas the second day of May, the next to last day o...Twas the second day of May, <BR/>the next to last day of class<BR/>We sat pondering the final, <BR/>and hoped we might pass.<BR/>The door flew wide open <BR/>and then proclaimed Satish:<BR/>I've got complexity theory <BR/>that I must unleash!"<BR/><BR/>NP was defined <BR/>and Cook's theorem was stated:<BR/>"If you can solve 3SAT, <BR/>this whole field's antiquated."<BR/>And though it's a worthy pursuit, <BR/>showing P =NP,<BR/>I think I'll leave that task <BR/>to someone smarter than me.<BR/><BR/>But an approximate solution! <BR/>Wouldn't that be great?<BR/>You can't win them all, <BR/>but how about seven of eight?<BR/>This proved to be easy, <BR/>we've got this one wired:<BR/>Conditionally assign, <BR/>and negate if required.<BR/><BR/>But theorists are greedy-- <BR/>I'm a 3SAT whore,<BR/>Surely it's no trouble <BR/>to satisfy a few clauses more<BR/>In pursuit of this goal, <BR/>PCP was defined.<BR/>(And I don't mean the drug, <BR/>though it's just as harsh on the mind.)<BR/><BR/>From PCP we proceed <BR/>with some clever deduction<BR/>and return to > 7/8 3-SAT <BR/>via complexity reduction.<BR/>So what's the big deal? <BR/>What course have we charted?<BR/>Turns out PCP = NP <BR/>and we're back where we started.<BR/><BR/>Mark PiloffGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112718481504511692005-04-05T11:28:00.000-05:002005-04-05T11:28:00.000-05:003SAT is NP-complete,say complexity theory elite.Bu...3SAT is NP-complete,<BR/>say complexity theory elite.<BR/>But watch PCP -<BR/>It covers NP,<BR/>and randomized checkers are sweet.<BR/><BR/>We randomly sample the proof<BR/>but aren't so easy to spoof.<BR/>Just make the proof bigger,<BR/>and somehow we figure<BR/>The storage won't go through the roof.<BR/><BR/>Dennis GeelsGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112717950146850832005-04-05T11:19:00.000-05:002005-04-05T11:19:00.000-05:00The next four posts are froma course called CS270....The next four posts are from<BR/>a course called CS270.<BR/>They are not mine, but are<BR/>in my files.<BR/><BR/>These are from a course CS270.<BR/>I don't know where the course was taught,<BR/>But it sounds like fun<BR/>For poet laureate I would have fought<BR/>But all I can do is pun.<BR/><BR/><BR/><BR/>There once were a tough set of problems;<BR/>Many theorists tried hard to solve 'em.<BR/>But all they e'er say<BR/>Was, "Just give me a way<BR/>To solve one and I'll have solved all of 'em."<BR/><BR/>One clever young theorist said, "Gee!<BR/>I'll define a new type called PCP."<BR/>So he did some contemplation,<BR/>Spent many days on calculation,<BR/>And finally said, "Damn, it's no simpler than NP!"<BR/><BR/>Nemanja IsailovicGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112716845956418742005-04-05T11:00:00.001-05:002005-04-05T11:00:00.001-05:00E PERCY PPercy P was a mathematician whose ...E PERCY P<BR/><BR/>Percy P was a mathematician<BR/> whose "pureness" was never denied.<BR/>But he found one day, to his sorrow,<BR/> that his theorems had been applied!<BR/>He had used all the standard precautions;<BR/> his papers were pointedly dry!<BR/>But his own esoteric notation<BR/> had been solved by a physicist spy!<BR/><BR/>The colloquium buzzed with the gossip;<BR/> he could offer no valid excuse.<BR/>Percy P was a traitor of traitors,<BR/> for his work was of PRACTICAL USE!<BR/>Nobody dared to defend him.<BR/> Could it be that he'd plead the crime<BR/>That his work was just then needed<BR/> to effect quantization of time?<BR/><BR/>Ignored when he joined conversations;<BR/> one would think that he poisoned the air.<BR/>And he felt on his way to the office -<BR/> a new man might be in his chair.<BR/>A committee was in operation,<BR/> working twenty four hours a day,<BR/>Deleting his name from the journals,<BR/> and throwing his reprints away.<BR/><BR/>He knew where his future was leading,<BR/> no sense in prolonging the pain;<BR/>He left with a handful of papers,<BR/> and never was heard from again.<BR/>So take heed all you mathematicians<BR/> who pretend your endeavor is pure;<BR/>Tho' your luck may hold for a decade,<BR/> in the end you can never be sure.<BR/>~ <BR/>~ <BR/><BR/>Note- this is not mine<BR/>Its just in my files<BR/>But I think its good<BR/>Even though it goes on for miles<BR/><BR/>~GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112716816650571362005-04-05T11:00:00.000-05:002005-04-05T11:00:00.000-05:00Haiku for P�l Erd?s"My brain is open,"Pali b�csi u...Haiku for P�l Erd?s<BR/><BR/>"My brain is open,"<BR/>Pali b�csi used to say<BR/>"Let n be a prime..."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112716591681763492005-04-05T10:56:00.000-05:002005-04-05T10:56:00.000-05:00Integral z-squared dzfrom 1 to the cube root of 3t...Integral z-squared dz<BR/>from 1 to the cube root of 3<BR/>times the cosine<BR/>of three pi over 9<BR/>equals log of the cube root of 'e'.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112716451015380282005-04-05T10:54:00.000-05:002005-04-05T10:54:00.000-05:00We're always eager to produce a new result ...We're always eager to produce a new result Even if an oracle we must consult <BR/> <BR/>For though $P=NP$ is ever open <BR/>To solve it we're still hopin'<BR/><BR/>And though exponential search we despise<BR/>We're not afraid to relativize<BR/><BR/>For we will never weary<BR/>Of computer science theory<BR/><BR/>Conference on Computational Complexity Theory<BR/> March 1983<BR/>Santa Barbara, California<BR/>(This was precuror to the current COMPLEXITY THEORY conference.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112685127369558422005-04-05T02:12:00.000-05:002005-04-05T02:12:00.000-05:00scratch that, that _would_ have read aleph_1 with ...scratch that, that _would_ have read aleph_1 with unicode support had my browser and/or blogger not decided to eat the unicode and spit out question marks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112684285434288862005-04-05T01:58:00.000-05:002005-04-05T01:58:00.000-05:00But, but, I know of a song which is strictly longe...But, but, I know of a song which is strictly longer than that one -- "?? bottles of beer on the wall."<BR/><BR/>(That should read aleph_1 with unicode support)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112676879584121942005-04-04T23:54:00.000-05:002005-04-04T23:54:00.000-05:00I was reminded of this poem whenI saw your post......I was reminded of this poem when<BR/>I saw your post... A poem by<BR/>Samuel Coleridge to his brother<BR/>on the construction of an equilateral triangle... and proof<BR/>that the construction is right.<BR/><BR/>If a proof must be beautiful, none<BR/>is better than one that rhymes.<BR/><BR/>This is now--this was erst,<BR/>Proposition the first--and Problem the first.<BR/><BR/>I<BR/><BR/>On a given finite Line<BR/>Which must no way incline;<BR/>To describe an equi--<BR/>--lateral Tri--<BR/>--A, N, G, L, E.<BR/>Now let A. B.<BR/>Be the given line<BR/>Which must no way incline;<BR/>The great Mathematician<BR/>Makes this Requisition,<BR/>That we describe an Equi--<BR/>--lateral Tri--<BR/>--angle on it:<BR/>Aid us, Reason--aid us, Wit!<BR/><BR/>II<BR/><BR/>From the centre A. at the distance A. B.<BR/>Describe the circle B. C. D.<BR/>At the distance B. A. from B. the centre<BR/>The round A. C. E. to describe boldly venture.<BR/>(Third Postulate see.)<BR/>And from the point C.<BR/>In which the circles make a pother<BR/>Cutting and slashing one another,<BR/>Bid the straight lines a journeying go,<BR/>C. A., C. B. those lines will show.<BR/>To the points, which by A. B. are reckon'd,<BR/>And postulate the second<BR/>For Authority ye know.<BR/>A. B. C.<BR/>Triumphant shall be<BR/>An Equilateral Triangle,<BR/>Not Peter Pindar carp, not Zoilus can wrangle.<BR/><BR/>III<BR/><BR/>Because the point A. is the centre<BR/>Of the circular B. C. D.<BR/>And because the point B. is the centre<BR/>Of the circular A. C. E.<BR/>A. C. to A. B. and B. C. to B. A.<BR/>Harmoniously equal for ever must stay;<BR/>Then C. A. and B. C.<BR/>Both extend the kind hand<BR/>To the basis, A. B.<BR/>Unambitiously join'd in Equality's Band.<BR/>But to the same powers, when two powers are equal,<BR/>My mind forbodes the sequel;<BR/>My mind does some celestial impulse teach,<BR/>And equalises each to each.<BR/>Thus C. A. with B. C. strikes the same sure alliance,<BR/>That C. A. and B. C. had with A. B. before;<BR/>And in mutual affiance,<BR/>None attempting to soar<BR/>Above another,<BR/>The unanimous three<BR/>C. A. and B. C. and A. B.<BR/>All are equal, each to his brother,<BR/>Preserving the balance of power so true:<BR/>Ah! the like would the proud Autocratorix do!<BR/>At taxes impending not Britain would tremble,<BR/>Nor Prussia struggle her fear to dissemble;<BR/>Nor the Mah'met-sprung Wight,<BR/>The great Mussulman<BR/>Would stain his Divan<BR/>With Urine the soft-flowing daughter of Fright.<BR/><BR/>IV<BR/><BR/>But rein your stallion in, too daring Nine!<BR/>Should Empires bloat the scientific line?<BR/>Or with dishevell'd hair all madly do ye run<BR/>For transport that your task is done?<BR/>For done it is--the cause is tried!<BR/>And Proposition, gentle Maid,<BR/>Who soothly ask'd stern Demonstration's aid,<BR/>Has prov'd her right, and A. B. C.<BR/>Of Angles three<BR/>Is shown to be of equal side;<BR/>And now our weary steed to rest in fine,<BR/>'Tis rais'd upon A. B. the straight, the given line. <BR/>-S.T.ColeridgeAnonymousnoreply@blogger.com