## The Knowledge Complexity Of Interactive Proof Systems-Free PDF

• Date:31 Jul 2020
• Views:0
• Pages:14
• Size:1.32 MB

Share Pdf : The Knowledge Complexity Of Interactive Proof Systems

Download and Preview : The Knowledge Complexity Of Interactive Proof Systems

Report CopyRight/DMCA Form For : The Knowledge Complexity Of Interactive Proof Systems

Transcription:

input a string Y belongingto an NP language provingprocedure Howcvcr NP only capturesa par. L A computesa string y whose length is ticular way of communicatinga proof It dealswith. bounded by a polynomial in the lcngtb of X those proofs that can be written down in a book. and writesy on a specialtape that B can read In this paper we introduce interactiveproof systems. B then checksthat fLib x where f is a to capture a more gcncral way of communicatinga. polynomial timecomputablefunction relativeto proof We deal with those proofs that can be. the language1 and if so halts and accepts explained in class Informally in a classroom the. This processis illusuatcdin figure 1 lecturer can take full advantageof the possibilityof. interacting with the recipients of the proof They, may ask questionsat crucial points of the argument. and receive answers This makes life much easier,Writing down a proof that can be checkedby every. body without interaction is a much harder task In,somesense becauseone hasto answerin advanceah. possiblequestions Let us now formally set up the,propercomputationalmodel. 2 1 InteractiveTuring machinesand interactivepairs. Fig 1 The Nf proof system of Turing machines,What is intuitively required From a theorem.
proving procedure First that it is possible to,prove a true theorem Sccomd that it is impossible. to prove a false theorem Third that communicat, ing a proof shouldbe cfhcient in the following sense. It doesnot matter how long must the provercompute, during the proving process but it is essentialthat the. computationrcquircd from tbc verifier is easy,Theorem proving procedures differ in the. underlying definition of a proof The notion of a, proof like the notion of a computation is an intuitive Fig 2 an interactivepair f Turing machines.