E mail and the unexpected power of interaction L6szld Babai Eotvos University Budapest and The University of Chicago Abstract Of course not even a tiny fraction could fit in the throne room but Arthur wouldn t even wait till the room filled up He dismissed Merlin s procedure obviously you overlooked a case and ordered him to come back with a solution the next day Arthur s diaries reveal another thought that was on his mind The lifetime of the universe wouldn t suffice to check all that crud That s how the old fox wants to fool me Merlin knew that he was right and he knew also that Arthur was reasonable All Merlin had to do was to convince him in five minutes that there was no solution Fortuitously in the cafeteria he bumped into an unassuming character dressed in brand new blue jeans An East Bloc visitor the man humbly introduced himself as DCnes Konig number one expert on perfect matchings Frobenius also claims this title he added without bitterness Are you perhaps interested in my mini max theory Having at last found a willing listener the visiting scholar forgot his French fries and the free ketchup and began a passionate lecture about bipartite graphs maximum matchings and minimum covers His new acquaintance was not the least bothered by his heavy accent and large gestures Before long Merlin found out that all he had to look for was a Konig obstacle a set of k knights all whose hearts burn for only k 1 ladies Merlin immediately saw that indeed there was such an obstacle k 79 With some assistance from the hardly brilliant but quite reliable court astronomer Arthur managed rapidly to check that the set of 79 knights indeed formed a Konig obstacle Being thereby convinced of Merlin s truth Arthur resigned to the impossibility of a perfect matching and began exploring other avenues to improve society The chronicles report that Merlin did not have to wait long for his next call One of Arthur s recent innovations had been the in This is a true fable about Merlin the infinitely intelligent but never trusted magician and Arthur the reasonable but impatient sovereign with an occasional unorthodox request about the concept o f an efficient proof about polynomials and interpolation electronic mail coin flipping and the incredible power of interaction About M I P I P P p PSPACE N E X P T I M E and new techniques that do not relativize About fast progress fierce competition and e mail ethics 1 How did Merlin end up in the cave In the court of King Arthur there lived 150 knights and 150 ladies Why not 150 married couples the King contemplated one rainy afternoon and action followed the thought He asked the Royal Secret Agent RSA to draw up a diagram with all the 300 names indicating bonds of mutual interest between lady and knight by a red line and the lack thereof by a blue line The diagram with its 150 22 500 colored lines looked somewhat confusing yet it should not confuse Merlin the court magician to whom it was subsequently presented by Arthur with the express order to find a perfect matching consisting exclusively of red lines Merlin walked away looked at the diagram and with his unlimited intellectual ability immediately recognized that none of the 150 possibilities gave an all red perfect matching He quickly completed the 150 diagrams highlighting the wrong blue line in each and ordered the servants t o carry them into the throne room as evidence that Arthur had asked the impossible Partially supported by NSF Grant CCR 871007 For general background we refer to Ma and BaM CH2899 3 90 0000 0030 01 OO 0 1990 IEEE 30 Authorized licensed use limited to IEEE Xplore Downloaded on October 15 2008 at 13 17 from IEEE Xplore Restrictions apply troduction of forks at meals When the Round Table was set for dinner the noble knights were invited to leave their swords and take their assigned seats Some of them savored the juicy legs of mutton that they could reach with the sturdy forks Others however discovered more knightly uses of the new utensils and wasted no time settling scores with their neighbors It seemed to Arthur that table manners could improve considerably with the right seating of the knights As before he proceeded to call the RSA who produced a graph indicating who will sit in peace next to whom Subsequently the task of finding an appropriate seating arrangement a Hamilton cycle in this graph as it came to be called later was assigned to Merlin When Merlin saw that there was no solution he no longer tried the 150 diagrams trick he just wrote to Konig but either the mail w a s too slow or there was some other obstacle Konig s reply to this letter never arrived Being unable to produce a solution by the deadline Merlin was sentenced to the gallows That sentence was immediately commuted to eternity in the cave up for parole when 1 3 served 2 environment Would anyone mind proving a theorem I could base my thesis on I am looking for a simple proof that there are infinitely many composite numbers Etc But then came a message with a more limited distribution and Merlin was pleased to see himself listed among the three dozen recipients or so It took him a little while to appreciate fully how pleased he ought to be Date Wed 13 Dec 89 13 38 05 0800 From fortnow0gargoyle uchicago edu Lance J To condon0cs wisc edu Jf0coma att com ode shafi0theory lcs mit edu tompa0cs w shamir0wisdom weizmann ac i1 sipser watanabe0cs titech ac jp rackoff0th merlinQcave nyneve gov avi0hujics h boyar daimi dk aiello0flash bellcor Subject IP contains PH documentstyleCliptl article setlength topmargin 5in set length t exthe ightI 9 in December 13 1989 setlengthC leftmargin C4 5em C end list33 beginCdocument begin cent er LARGE bf The Polynomial Time Hierarchy has Interactive Proofs The centuries passed in gray monotony Merlin s only delights were the birds chirping at his window and an occasional message through e mail Meanwhile he conducted some theoretical studies and became proficient with MACSYMA He heard about the CookLevin theorem through questions posted on a bulletin board and came to be resigned to the recognition that the conjecture N P c o N P if true would allow the possibility that there was no way for him to ever convince Arthur At least so it seemed until December 13 1989 On this historic date the weather was unusually agreeable maybe a sign of global warming but this did not prevent Merlin from having a late afternoon nap according to his daily routine When he awakened he went to the workstation to