Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Proof Verification and Approximation Algorithms	Prologue

Prologue

(1)	The exam consists of q yes/no questions.
(2)	A student passes if and only if he or she answers all questions correctly.

You assume that, on average, you'll need at least half a second to check the correctness of each answer. Since you expect the number of students to be close to one thousand (it is a very popular basic course!), and since the number of questions will be several hundreds a rough estimate shows that you are going to spend almost a whole week grading the exam. Uff.

Is there a faster way?

Certainly not in general: in the worst case you really might have to look at all s·q answers in order to rule out a false decision. But what, if we relax the second condition slightly and replace it by

(2')	A student definitely passes the exam if he or she answers all questions correctly. A student who does not answer all questions correctly may pass only with a small probability, say < 10-3, independently of the answers he or she gives.

Now you suddenly realize that the grading can actually be done in about 45s seconds, even regardless of the actual number q of questions asked in the exam. That is, a single day should suffice. Not too bad.

How is this possible? Find out by reading this book! And enjoy!