Interactive Proof Systems
In the realm of complexity theory, NP is defined based on languages that have polynomial time verifiers. These verifiers utilize additional information called certificates to verify membership in a language. Interactive Proof Systems delve into the intricacies of validating languages through a variety of formulations, offering a deeper understanding of the complexities of computational decision problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ECE461: Theoretical CS Interactive Proof Systems
Brief Recap Earlier in the course, we discussed topics related to computability theory, which relates to the question of which languages (or, alternatively, decision problems) are decidable Our primary models of computation have been deterministic Turing machines (DTMs) and nondeterministic Turing machines (NTMs) If we accept the Church-Turing thesis, all algorithms can be implemented by Turing machines Then we started to cover complexity theory, which explores which languages can be decided efficiently We introduced time and space complexity classes; two important time complexity classes are P P and NP which are believed to be different, but the P P versus NP NPquestion has never been solved We also learned that some languages are intractable; the NP-complete problems are probably intractable, but we don't know for sure We also learned about space complexity classes, such as PSPACE that PSPACE = NPSPACE In our last topic, we added randomization to our TM model; TMs that rely on randomness are known as probabilistic Turing machines, and they implement probabilistic algorithms We defined the complexity class BPP BPP, which includes languages that can be decided in polynomial time with a small error probability in both directions; it is unclear if BPP includes any languages that are not in P NP, PSPACE; one consequence of Savitch's theorem is
NP, Verifiers, and Certificates (revisited) Recall that the complexity class NP had two formulations One formulation of NP is based on Definition 7.19 of the textbook, which states: "NP is the class of languages that have polynomial time verifiers." A second formulation is stated by Theorem 7.20: "A language is in NP iff it is decided by some nondeterministic polynomial time Turing machine." The first formulation is the one that is more relevant to our current topic Definition 7.18 states (I am keeping the textbook's exact wording, but changing the formatting a bit): A verifier for a language A is an algorithm V , where A = {w| V accepts w, c for some string c}. We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs in polynomial time in the length of w. A language A is polynomially verifiable if it has a polynomial time verifier. The book refers to c as "additional information" used by the verifier to verify that the string, w, is a member of the language, A Book: "This information is called a certificate, or proof, of membership in A."
Interactive Proof Systems This topic is based on Section 10.4 of the textbook The textbook says that probabilistic Turing machines (covered during our previous topic), which implement probabilistic algorithms, provide "a probabilistic analog to P" They introduce interactive proof systems to "provide a way to define a probabilistic analog of NP" An interactive proof system can be casually defined as follows: An interactive proof system includes a Verifier and a Prover (I am following the book's convention to capitalize these terms in this context) The Verifier must implement a polynomially bounded algorithm, but it is allowed to rely on randomization, and it is allowed to accept or reject its input with a small error probability The Prover has no computational bound The Verifier and the Prover are allowed to interact, using a convention we will explain more formally soon The job of the Prover is to convince the Verifier to accept its input (i.e., it tries to convince the Verifier that its input, w, is a member of the language it is attempting to verify) The Verifier does not necessarily trust the Prover, which may not be an honest broker; that is, the Prover is trying to convince the Verifier to accept w regardless of whether w is truly a member of the language Book: "The development of interactive proof systems has profoundly affected complexity theory and has led to important advances in the fields of cryptography and approximation algorithms."
NONISO (part 1) Before we formally define interactive proof systems, we will explain the concept via an example Two graphs, G and H, are isomorphic "if the nodes of G may be reordered so that it is identical to H" The textbook defines the language: ISO = {<G, H> | G and H are isomorphic graphs} Book: "Although ISO is obviously in NP, extensive research has so far failed to demonstrate either a polynomial time algorithm for this problem or a proof that it is NP-complete." I add: The reason ISO is obviously in NP is that we can provide a certificate showing how the vertices of one graph can be reordered in such a way as to be identical to the other graph The book continues: "It is one of a relatively small number of naturally occurring languages in NP that haven t been placed in either category." The book then defines the complementary language: NONISO = {<G, H> | G and H are not isomorphic graphs} Book: "NONISO is not known to be in NP because we don't know how to provide short certificates that graphs aren't isomorphic." Later in the section, the book also point out that NONISO is not known to be in BPP Nonetheless, we can set up an interactive proof system in which a Prover can convince a Verifier that two graphs are not isomorphic (and hence, the pair is a member of the language NONISO)
NONISO (part 2) Recall that a Prover has unbounded computational abilities Therefore, a Prover can try out all permutations of one graph, G1, to determine if it is identical to G2 A Prover could convince a Verifier of membership in ISO by precenting the appropriate reordering (this would be a standard certificate) Now let's consider the case where G1and G2are not isomorphic A Prover could determine this by trying out all permutations and seeing that they all fail However, a Prover cannot just declare that G1and G2are non-isomorphic and accept a Verifier to accept this, because the Verifier would not trust the Prover However, an interactive proof system can be constructed whereby a Prover can convince a Verifier that two graphs are non-isomorphic as follows The Verifier can randomly select either G1or G2, and randomly reorder its nodes to obtain a new graph, H The Verifier can send a message to the Prover, asking it to predict if H was created from G1or G2 If G1and G2are not isomorphic, the Prover will be able to figure out the right answer every time If G1and G2are isomorphic, the Prover will be forced to take a guess, with a probability of guessing right If this process is repeated many times (e.g., 100 times), and the Prover gets the right answer every time, the Verifier should be convinced that the two graphs are almost certainly non-isomorphic
Interactive Proof Systems: The Verifier The book formally defines the Verifier "to be a function V that computes its next transmission to the Prover from the message history sent so far" The function, V, has three inputs: The input string This is what we typically think of as an input to a verify It is some string, w, and the Verifier needs to determine if w is a member of some language Random input Rather than give the Verifier the ability to do coin flips, as with a probabilistic TM, they hypothesize that V is given a "randomly chosen input string" we will call r The book does not specify r's alphabet, but I think it contains random bits, analogous to fair coin flips The book explains that the length of r is p(n), where p(n) is the upper bound for the total number of messages exchanged between the Verifier and the Prover Partial message history These are all the messages sent between the Verifier and the Prover so far The format is m1#m2#...#mi, where i is the number of messages sent so far The output of V is either the next message, mi+1, or accept or reject; so, the function V has the form: V: * x * x * * {accept, reject}
Interactive Proof Systems: The Prover Book: "The Prover is a party with unlimited computational ability" I would like to add a couple of thoughts about this: A prover is unbounded in terms of space and time, but I believe it still must apply computation (i.e., something that can be done by a TM) to determine its messages This is not the same as an oracle, which we can posit even for undecidable problems I have seen some online sources claim that the Prover can be allowed to compute undecidable functions, but this does not seem consistent to me Perhaps allowing the Prover to compute undecidable functions wouldn't change membership in IP (to be discussed soon), because the Verifier doesn't trust the Prover anyway Also, a Prover does not have access to, or knowledge of, r, the random string used by V They define the Prover "to be a function P with two inputs"; the inputs are: The input string this is the same input string, w, available to the Verifier Partial message history this is the same message history that is available to the Verifier The output of P is always the next message, mi+1; so, the function P has the form: P: * x * *
Interactive Proof Systems: Interaction Next, the book formally defines the way that interaction works between the Verifier and Prover (I am keeping the book's exact wording): For particular strings w and r, we write (V P)(w, r) = accept if a message sequence m1through mkexists for some k whereby 1. for 0 i < k, where i is an even number, V (w, r, m1# #mi) = mi+1; 2. for 0 < i < k, where i is an odd number, P(w, m1# #mi) = mi+1; and 3. the final message mkin the message history is accept. The book also defines for any string w of length n (I am keeping book's exact wording but modifying the format a bit): Pr[V P accepts w] = Pr[(V P)(w, r) = accept], where r is a randomly selected string of length p(n) I have a few thoughts about the interaction and definitions here: Note that V produces messages on even numbered turns (starting at 0) and P produces messages on odd numbered turns; the messages are exchanged until the Verifier makes a decision I'm sure that they could define an analogous notation for what happens when the system rejects I think, in general, it is probably possible for a Verifier to loop forever, but we will only be considering polynomial time verifiers, which means that they ultimately accept or reject within polynomial time Once r (which has been randomly generated) is provided, everything from that point on is deterministic, so the interactive proof system will either accept or reject deterministically, given r
IP Now we will define a complexity class called IP IP Based on online sources, IP stands for "interactive polynomial time", although the type of system we are dealing with is an "interactive proof" system) Definition 10.28 states (I am keeping the book's exact wording): Say that language A is in IP if some polynomial time computable function V exists such that for some (arbitrary) function P and for every (arbitrary) function P and for every string w, 1. w A implies Pr[V P accepts w] , and 2. w A implies Pr[V P accepts w] . This definition states two facts that the book casually summarizes as: " if w A then some Prover P (an 'honest' Prover) causes the Verifier to accept with high probability" " if w A, then no Prover (not even a 'crooked' Prover P) causes the Verifier to accept with high probability" As with probabilistic Turing machines (discussed during our previous topic), we can amplify the probability of a correct decision by repetition, making the error probability as small as we desire Book: "Obviously, IP contains both the classes NP and BPP"; I add: this is clear because: IP contains NP because a Prover could provide the certificate to the Verifier (no further interaction is needed) IP contains BPP because the Verifier has all the abilities of a probabilistic TM (no interaction is needed)
IP = PSPACE (part 1) We now know that IP contains BPP and NP Recall that, near the start of the topic, we saw that IP contains NONISO, which is not known to be in either NP or BPP Of course, this leads to the question: How big is the IP complexity class? Theorem 10.29 states: "IP = PSPACE" The textbook calls this "one of the more remarkable theorems in complexity theory" This theorem was first proved by Shamir in 1990, who presented his preliminary results at a conference that year Shamir was building upon recent results by Lund, Fortnow, Karloff, and Nisan, who also first published their preliminary results (jointly) in 1990 The Arora and Barak book explains that, prior to this, it was known that NP IP PSPACE They state that there was evidence that the first containment was proper, and that most computer scientists had an expectation that both containments were likely proper They state that the theorem being discussed shows "that this intuition was drastically wrong" I add: Recall we still don't know for certain that NP PSPACE, or even that P PSPACE!
IP = PSPACE (part 2) The Sipser textbook splits the proof of the theorem "into lemmas that establish containment in each direction" Lemma 10.30 states: "IP PSPACE" Lemma 10.32 states: "PSPACE IP" Of course, if we prove both lemmas, we have proven Theorem 10.29 The textbook proves both lemmas with detailed proofs In class, we will only discuss the high-level details of each direction
IP = PSPACE (part 3) The textbook's proof that IP PSPACE is a constructive proof, presenting a polynomial space algorithm to compute the probability that a given verifier will accept a given input string, w Along the way, we see that polynomial space is enough to do all the following things: To examine every possible random string, r, of length p(n) To examine every possible sequence of p(n) polynomial-length messages To determine if a sequence of messages is consistent with r To determine whether a Verifier, V, would accept w given a sequence of messages Note that things don't actually happen in the order listed above; the algorithm roughly proceeds as follows: First, it computes the probabilities that V accepts w given full message sequences (each is either 0 or 1) Then, it iteratively computes the probabilities that V accepts w given all possible partial message sequences (each involves computing a weighted average or taking a max, depending on whose turn it is to produce the next message) Finally, the algorithm computes the probability that V accepts w starting with an empty sequence of messages It seems to me that the proof in the book leaves out an important point If w is a member of the language, A, being probabilistically decided, the probably that the Verifier accepts w will be greater than 2/3, given that A IP If w is not a member of the language, A, being probabilistically decided, the probably that the Verifier accepts w will be less than 1/3, given that A IP
IP = PSPACE (part 4) The textbook's proof that PSPACE IP is significantly more complicated, occupying about 7 pages in the book; we will only discuss it at a high level Along the way, they first that another problem is in IP The book defines the language: #SAT = { , k | is a cnf-formula with exactly k satisfying assignments} The textbook calls this the counting problem for satisfiability Based on other sources, this counting problem, a.k.a. Sharp-SAT, is often defined more generally, such that you are given and asked to determine k, the number of satisfying solutions for Note that the way the textbook defines it, if k is 0, this is the complement of SAT, which is coNP-complete To show that #SAT is in IP, the program introduces a technique called arithmetization At a high level, the cnf-formula, , along with k, is converted to a series of formulas that can be fed randomly chosen integer parameters The computed values of the functions are guaranteed to satisfy certain constraints, if has exactly k solutions When is not satisfiable, the Prover is forced to lie to prevent the Verifier from rejecting Unless the Prover gets lucky, its lies will get caught in the final phase of the algorithm The textbook then shows how a more complex version of this approach can be used to prove that TQBF is in IP (the details of the algorithms for both #SAT and TQBF are in the book) Since TQBF is PSPACE-complete, this proves that all PSPACE problems are in IP
