Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!cmcl2!yale!leichter
From: leichter@yale.UUCP (Jerry Leichter)
Newsgroups: sci.math
Subject: Re: P = NP
Message-ID: <4556@yale-celray.yale.UUCP>
Date: Mon, 24-Nov-86 12:58:59 EST
Article-I.D.: yale-cel.4556
Posted: Mon Nov 24 12:58:59 1986
Date-Received: Mon, 24-Nov-86 22:31:37 EST
References: <1953@emory.UUCP> <269@mipos3.UUCP> <403@cartan.Berkeley.EDU> <863@ur-valhalla.UUCP>
Reply-To: leichter@yale-celray.UUCP (Jerry Leichter)
Organization: Yale University, New Haven, CT
Lines: 25


Badri Lockanathan expresses skepticism at the notion of a "zero knowledge
proof".  Nevertheless, the references to this notion are real and valid;
there's a lot of very clever, hard work behind it all.

The intuitive idea is fairly simple; you should look at the actual papers for
the technical details.

Consider a predicate P.  A zero-knowledge proof for P can be looked at as
an oracle that answers various questions with yes/no answers; the answers,
taken together, can be used to prove that P is true.  The proof is zero-
knowledge if, given a pair of Turing machines S and T, where S can call the
oracle with a polynomial number of questions, and T can call on another oracle
that answers only one question:  Is P true? (which it answers YES), then T
and S can write down proofs for exactly the same set of formulas.

The FROM of the predicates that one is concerned with might be exemplified
by:  P = {N is a product of exactly two primes}.  (Don't take this as a
LITERAL example!)  A zero-knowledge proof of P would convince you that it
was true, but would not provide you with ANY information that would help
you factor N.  That is:  If you could factor N given such a proof, then you
could have simply started with the assumption that N was of this form and,
if that assumption happened to be true, factored just as easily.

							-- Jerry