Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!husc6!hao!ames!ucbcad!ucbvax!ernie.Berkeley.EDU!tedrick
From: tedrick@ernie.Berkeley.EDU (Tom Tedrick)
Newsgroups: sci.philosophy.tech
Subject: Re: Complexity Philosophy
Message-ID: <19257@ucbvax.BERKELEY.EDU>
Date: Sat, 6-Jun-87 06:48:40 EDT
Article-I.D.: ucbvax.19257
Posted: Sat Jun  6 06:48:40 1987
Date-Received: Wed, 10-Jun-87 03:56:44 EDT
References: <8706041841.AA14805@brahms.Berkeley.EDU>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: tedrick@ernie.Berkeley.EDU.UUCP (Tom Tedrick)
Organization: University of California, Berkeley
Lines: 45

>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.  Thus, at the time they
>all knew that Tartaglio (or was it his buddy Cardano?) had proven that
>cubic equations were solvable, and similarly they knew that Pell's equa-
>tion was solvable by Fermat, but they did not infer much about what the
>actual proofs were.

A few points that occur to me:

(1). Was the method completely general? Were they able to convince their
     collegues that they had a proof, for every theorem they came up
     with, without giving away any further information about the proof?

(2). Could they prove that their methods of convincing their collegues
     gave away absolutely no extra information about the proofs?

(3). Could they prove that they really had a proof, not just some luck
     or some clever trick? Could they give precise bounds on the
     probability that they had a proof?

People tried to give demonstrations before formal logic, still formal
logic was a blindingly brilliant discovery.

>But seriously, Tom, this isn't a new notion of proof, but of mathematical
>epistemology.

Could you explain in more detail? I don't think I understand what
you mean.

>Even the Einsteins and Goedels are not irreplaceable for the advances in
>our knowledge that they discovered.

I'm not so sure about that. I don't know the official name for my
philosophical position (catastrophe theorist? :-) but I am inclined
to the view that the acts of one individual can radically alter the
course of human affairs.

By the way, have you talked to Solovay about these 0-knowledge creatures?