Jump to ContentJump to Main Navigation
The Nature of Computation$
Users without a subscription are not able to see the full content.

Cristopher Moore and Stephan Mertens

Print publication date: 2011

Print ISBN-13: 9780199233212

Published to Oxford Scholarship Online: December 2013

DOI: 10.1093/acprof:oso/9780199233212.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 26 November 2020

Interaction and Pseudorandomness

Interaction and Pseudorandomness

(p.506) (p.507) Chapter 11 Interaction and Pseudorandomness
The Nature of Computation

Cristopher Moore

Stephan Mertens

Oxford University Press

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.

Keywords:   randomness, prover, verifier, graphs, pcp Theorem, proofs, randomised algorithms, pseudorandomness, derandomisation, hardness

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .