dc.contributor.author Hartmanis, Juris en_US dc.contributor.author Chang, Richard en_US dc.contributor.author Ranjan, Desh en_US dc.contributor.author Rohatgi, Pankaj en_US dc.date.accessioned 2007-04-23T17:47:46Z dc.date.available 2007-04-23T17:47:46Z dc.date.issued 1990-05 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1129 en_US dc.identifier.uri https://hdl.handle.net/1813/6969 dc.description.abstract Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible computations. Furthermore, the IP = PSPACE result reveals some very interesting and unsuspected properties of mathematical proofs. In this column, we define the width of a proof in a formal system $\cal F$ and show that it is an intuitively satisfying and robust definition. Then, using the IP = PSPACE result, it is seen that the width of a proof (as opposed to the length) determines how quickly one can give overwhelming evidence that a theorem is provable without showing the full proof. en_US dc.format.extent 1054474 bytes dc.format.extent 235567 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title On IP=PSPACE and Theorems with Narrow Proofs en_US dc.type technical report en_US
﻿