期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：This in the fifth version of our work.
It is a revision and re-organization of the material in the previous version.
The first part of this paper presents our proof systems and
non-approximability results.
In particular we present a proof system for NP
using logarithmic randomness and two amortized free bits, so that Max Clique
is hard within N^{1/3} and Chromatic Number within N^{1/5}.
We also show hardness of 37/26 for MAX-3-SAT, 16/15 for Vertex Cover,
66/65 for Max-Cut, and 74/73 for MAX 2-SAT.
A key aspect of this part of our work is the introduction of the Long-Code
and tests for it.
The second part of this paper presents a ``reverse'' of the FGLSS connection
by showing that an NP-hardness result for the approximation of Max Clique to
within a factor of N^{1/(g+1)} would imply a probabilistic verifier for NP
with logarithmic randomness and amortized free-bit complexity g.
We also investigate some limitations of
``existing techniques'' for constructing proof systems of low
amortized free bit complexity.
Finally, we initiate a comprehensive study of PCP and FPCP parameters, proving
several triviality results and providing several useful transformations.
