@article {IOPORT.01456186,
    author       = {Dantsin, E.Ya.},
    title        = {Probabilistic verification of proofs in calculuses.},
    year         = {1997},
    journal      = {Journal of Mathematical Sciences (New York)},
    volume       = {98},
    number       = {4},
    issn         = {1072-3374},
    publisher    = {Springer, New York},
    doi          = {10.1007/BF02362268},
    abstract     = {Summary: We define a special kind of a probabilistically checkable proof system, namely, Probabilistically Checkable Proof calculuses (PCP calculuses). A proof in such a calculus can be verified with sufficient confidence by examining only one random path in the proof tree, without reading the whole proof. The verification procedure just checks all applications of inference rules along the path: its running time is assumed to be polynomial in the theorem length. It is shown that the deductive power of PCP calculuses is characterized as follows: (i) the decision problem for theorems is in PSPACE for all PCP calculuses; and (ii) the mentioned problem is PSPACE-hard for some of the calculuses.},
    identifier   = {01456186},
}