Interaction and Pseudorandomness
Cristopher Moore, Stephan Mertens · 2011
Abstract Although randomness can yield simple, efficient, and beautiful algorithms, it affects computation in many other ways. In NP problems, a ‘yes’ answer can be proven by the Prover to the Verifier. NP problems may be viewed as conversations between the Prover and the Verifier, in which the latter asks for a proof and the former responds with one. This chapter focuses on the Verifier and Prover in the form of Arthur and Merlin, whereby the former tries to convince the latter that two graphs are topologically different. It demonstrates how Arthur can keep Merlin honest by asking him random questions. It also considers the PCP Theorem, which shows that it is possible to check proofs for NP problems by looking at just a few bits. In addition, it examines whether randomised algorithms can be derandomised. It describes pseudorandomness and derandomisation before concluding by looking at the general connection between hardness and randomness.