tedrick@ernie.Berkeley.EDU (Tom Tedrick) (06/04/87)
Well, one example (out of many that I have pondered) of aspects of complexity theory that seem relevant to philosophy is the so-called "Zero Knowledge Interactive Proof Systems" (developed between 1983 and 1986 and currently a hot research area). Using these things you can prove (probabalistically, with exponentially small probability of error) that a theorem is true without giving away any new information about the proof, except that it exists. These things really bothered me when I first heard about them, but now I am kind of fascinated by them. 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.
obnoxio@BRAHMS.BERKELEY.EDU.UUCP (06/04/87)
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. 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. But seriously, Tom, this isn't a new notion of proof, but of mathematical epistemology. This reminds me of the Y/Yb "scandal" in that first paper about the new high-temperature superconductors, as reported in _Science_. There were very strong requests that Physical Review not leak any details out before publication, yet rumors of the ytterbium-based material ran around. Of course, those particular "Yb"s were a misprint for "Y", which coincident- ally never was spelled out. The proofs were corrected on the last poss- ible day. What happens to science when one knows that other people know stuff, but not much more? Does it fall apart? I doubt it, considering how frag- mented scientific knowledge is already without any malicious intentions. Even the Einsteins and Goedels are not irreplaceable for the advances in our knowledge that they discovered. ucbvax!brahms!weemba Matthew P Wiener/Brahms Gang/Berkeley CA 94720 Some billion years ago, an anonymous speck of protoplasm protruded the first primitive pseudopodium into the primeval slime, and perhaps the first state of uncertainty occurred. --I J Good
jfbuss@water.UUCP (06/06/87)
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.
tedrick@ernie.Berkeley.EDU (Tom Tedrick) (06/06/87)
>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?
obnoxio@BRAHMS.BERKELEY.EDU.UUCP (06/06/87)
More on Zero Information proofs: In article <19257@ucbvax.BERKELEY.EDU>, tedrick@ernie (Tom Tedrick) writes: >>>and now after 2000+ years all of a sudden a new notion of proof appears. > >>Hardly new. Renaissance mathematicians used to [play games with each other] >(1). Was the method completely general? [etc] No. No. And no. Of course not. These were all meant as *examples* of zero-information proofs, not the general theory. They could, at times, for certain problems, convince the mathematical community that they indeed knew a proof of certain problems. Just like: >People tried to give demonstrations before formal logic, still formal >logic was a blindingly brilliant discovery. Right. They could give proofs, without knowing what a "proof" in fact was. >>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. The zero information proofs still require that a proof in the classical sense be written out somewhere, which proof is then transformed into a clever graph-theoretic problem. What's different here is how one *knows* that a given theorem is known. >>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. Ah! Remember though, the course of human affairs is one thing, the sum total of human knowledge is another. I've often wondered just how diff- erent mathematics *could* be--unlike history, I think there would be no non-cosmetic differences, give or take a few decades. Look how often a great idea is rediscovered, or found to have strong precursors, etc. >By the way, have you talked to Solovay about these 0-knowledge creatures? Be serious. We rarely talk about anything *finite*! How droll. ucbvax!brahms!weemba Matthew P Wiener/Brahms Gang/Berkeley CA 94720