Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!jfbuss
From: jfbuss@water.UUCP
Newsgroups: sci.philosophy.tech
Subject: Re: Complexity Philosophy
Message-ID: <988@water.UUCP>
Date: Fri, 5-Jun-87 17:25:02 EDT
Article-I.D.: water.988
Posted: Fri Jun  5 17:25:02 1987
Date-Received: Sat, 6-Jun-87 12:00:55 EDT
References: <8706041841.AA14805@brahms.Berkeley.EDU>
Reply-To: jfbuss@water.UUCP (Jonathan Buss)
Organization: U. of Waterloo, Ontario
Lines: 29

In article <8706041841.AA14805@brahms.Berkeley.EDU> obnoxio@brahms.berkeley.edu (Obnoxious Math Grad Student) writes:
>In article <19233@ucbvax.BERKELEY.EDU>, tedrick@ernie (Tom Tedrick) writes
>about "Zero Knowledge Interactive Proof Systems", ie, methods of convincing
>anyone that you do indeed know a proof to something without giving out clues:
>
>>					  It seems to me that we
>>have had basically one notion of mathematical proof since Euclid,
>>and now after 2000+ years all of a sudden a new notion of proof appears.
>
>Hardly new.  Renaissance mathematicians used to pose problems to each
>other and not reveal their solution techniques.

Mathematicians are usually willing to believe the integrity and
cleverness of their colleagues (or at least to give the benefit of the
doubt).  But the claims of mathematicians are in no way proofs.  If
one is inclined to doubt the claimant, one can responsibly doubt the
claimed result.  If a "zero knowledge interactive proof" is given (in
the course of a conversation between a claimant and a doubter), then a
doubter who trusts probability theory and his source of random bits
(but is convinced the claimant is a lying whatever) will be stretched
to the limit to believe that an event with an a priori probability of
one in a googol just occurred.  But the falsity of the claim requires
such an event.

The "new" idea here is that a conversation might be an absolutely
convincing argument (a.k.a. "proof"), even though a transcript of the
conversation is not a proof.