Hi folks, welcome to my first foray in to mathematical blogging. This site exists to make me learn mathematics, and the best way to learn is to teach! To this end, I will be summarizing and giving my personal take on various textbooks, starting with "Computational Complexity: A Modern Approach." by Arora & Barak. Before I get to the maths, let me give two caveats.
The first is that to make it easier to publish (and because google blog doesn't support LaTeX), my math notation will be in ascii. I may even resort to english rather than standard mathematical notation (i.e. funny greek symbols). The second is that being a mere mortal, I may occasionally make mistakes in reasoning or explain things less clearly than I should. To fix this, comments and questions are most welcome. I will take them in to account when I write polished versions of these posts.
Right, enough of that. On to mathematics!
Thursday, 31 March 2011
Chapter 8 of Arora & Barak, Part 1.
Chapter 8 is about "interactive proofs", although this name may be misleading. If I talked about "interactive proofs" to a friend who for his own perverse reasons never studied computational complexity, he might envision the presentation of a proof during a seminar, the interactive part being that guests can interrupt and ask for clarification. Another possible interpretation is that the proof is presented on a computer, perhaps with java applets, and viewers are free to play with the hyperlinks and simulations.
The sense used in Arora & Barak is this: there are two players, the prover and the verifier. The prover's objective is to convince the verifier that some statement is true. The verifier's objective is to not be misled, or at least lower the probability of being misled to some acceptable margin, say 1/3rd. The verifier can ask a series of questions to the prover, and the prover provides some value in response, which the verifier can then verify, and perhaps ask further questions. The fun bit is in designing a protocol so that the verifier and prover can achieve their aims.
Let's define this more formally:
Intuitively, what's going on here is that f is the verifier, g is the prover, and f and g remember each round of interaction they had before. f asks k/2 questions (each question or answer is a round), g gives k/2 answers, and finally f makes a decision based on this conversation.
Armed with this mathematical notion of interaction, let's consider our first complexity class involving interactive proofs:
Tomorrow: I answer questions about what the hell I'm talking about, and prove that dIP is really just NP (making the word "interactive" a bit of a fib).
The sense used in Arora & Barak is this: there are two players, the prover and the verifier. The prover's objective is to convince the verifier that some statement is true. The verifier's objective is to not be misled, or at least lower the probability of being misled to some acceptable margin, say 1/3rd. The verifier can ask a series of questions to the prover, and the prover provides some value in response, which the verifier can then verify, and perhaps ask further questions. The fun bit is in designing a protocol so that the verifier and prover can achieve their aims.
Let's define this more formally:
Let f,g be functions on bit-strings and k be a non-negative integer. A *k-round interaction* of f and g on some input x, denoted by <f,g>(x) is the following sequence.
a1 = f(x)
a2 = g(x,a1)
a3 = f(x,a1,a2)
a4 = g(x,a1,a2,a3)
...
a(2i+1) = f(x,a1,...,a2i) for 2i < k
a(2i+2) = g(x,a1,...,a2i+1) for 2i+1 < k
...
The *output* of a k-round interaction is f(x,a1,...,ak); the output is assumed to be a single bit, 0 or 1.
Intuitively, what's going on here is that f is the verifier, g is the prover, and f and g remember each round of interaction they had before. f asks k/2 questions (each question or answer is a round), g gives k/2 answers, and finally f makes a decision based on this conversation.
Armed with this mathematical notion of interaction, let's consider our first complexity class involving interactive proofs:
A language L has a *k-round deterministic interactive proof system* if there's a program V, that on input x,a1,...,ai runs in time polynomial in the length of x, and can have a k-round interaction with any function P (even uncomputable ones), such that
If x is in L, there is some function P such that the output of a k-round interaction between V and P on input x is 1. (This is called the completeness property).
If x is not in L, for all functions P, the output of a k-round interaction with V and P on input x is 0. (This is called the soundness property).
The class dIP (deterministic Interactive Proof) contains all languages with a k(n)-round deterministic interactive proof system, where k(n) is polynomial in n.The completeness property means that we can always find some prover that will prove x is in L (assuming x is in fact, in L). The soundness property means that no matter which prover function we pick, if x isn't in L, then an interaction between the prover and the verifier will result in the verifier deciding that no, x is not in L.
Tomorrow: I answer questions about what the hell I'm talking about, and prove that dIP is really just NP (making the word "interactive" a bit of a fib).
Subscribe to:
Posts (Atom)