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.
This in the fourth version of our work.
It corrects some inaccuracies,
most notably an error in our MaxCUT non-approximability result which is
for constant 72/71 (rather than 66/65 as claimed before).
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.
This in a third version of our work. It contains improved
non-approximability results for all MaxSNP problems considered in the
previous versions.
The first part of this paper presents new proof systems and improved
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
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.
This is a revised version of ECCC TR95-024 of May 1995.
This paper continues the investigation of the connection between proof systems
and approximation. The emphasis is on proving {\em tight\/}
non-approximability results via consideration of measures like the ``free bit
complexity'' and the ``amortized free bit complexity'' of proof systems.
The first part of the paper presents a collection of new proof systems based
on a new error-correcting code called the long code, and means to test it. We
provide a proof system which has amortized free bit complexity of $2 +
\epsilon$, implying that approximating Max Clique within $N^{\frac13-\e}$,
and approximating the Chromatic Number within $N^{\frac15-\e}$,
are hard assuming $\NP\neq\coRP$, for any $\e>0$.
We also derive the first explicit and reasonable constant hardness factors
for Min Vertex Cover, $\MSAT{2}$, and Max Cut, and improve the hardness
factor for $\MSAT{3}$. We note that our
non-approximability factors for $\maxsnp$ problems are appreciably close to
the values known to be achievable by polynomial time algorithms. Finally
we note a general approach to the derivation of strong non-approximability
results under which the problem reduces to the construction of certain
``gadgets.''
The increasing strength of non-approximability results via the proof checking
connection motivates us to ask how far this can go, and whether proofs are
inherent in any way. This is addressed in the second part of the paper.
Recall that \cite{fglss} showed how to translate proof systems for $\NP$ into
$\NP$-hardness of approximation results for Max Clique. We begin with a
result of a novel nature which essentially reverses this connection, showing
how any $\NP$-hardness of approximation result yields a proof system for
$\NP$. Roughly our result says that for any constant $f$ if Max Clique is
$\NP$-hard to approximate within $N^{1/(1+f)}$ then $\NP$ is in the class
$\overline{\fpcp}[\log,f]$ of languages possessing proofs of logarithmic
randomness and amortized free bit complexity $f$. This indicates that proofs
are inherent to obtaining non-approximability results. But it does more: it
provides a tight relation indicating that to get large hardness factors we
must minimize the amortized free bit complexity. Motivated by this result we
look at how low the amortized free bit complexity can go. We show that a $2$
free bit complexity is inherent to verifiers constructed using ``current''
recursive proof verification techniques, and thus the long code is optimal for
its use here. In particular, new techniques are required to prove a better
than $N^{1/3}$ factor hardness for Max Clique.
The third part of our paper initiates a systematic investigation of the
properties of PCP and FPCP as a function of the various parameters:
randomness, query complexity, free bit complexity, amortized free bit
complexity, proof size, etc. We are particularly interested in ``triviality''
results which indicate which combinations of parameters are {\em not\/}
powerful enough to capture $\NP$. We also distill the role of randomized
reductions in this area, and provide a variety of useful transformations
between proof checking complexity classes.
This paper continues the investigation of the connection between proof
systems and approximation. The emphasis is on proving ``tight''
non-approximability results via consideration of measures like the
``free bit complexity'' and the ``amortized free bit complexity'' of
proof systems.
The first part of the paper presents a collection of new proof systems
based on a new error-correcting code called the long code, and means
to test it. We provide a proof system which has amortized free bit
complexity of $2 + \epsilon$, implying that approximating Max Clique
within $N^{\frac13-\epsilon}$, and approximating the Chromatic Number
within $N^{\frac15-\epsilon}$, are hard assuming $\NP\neq\coRP$, for
any $\epsilon>0$. We also derive the first explicit and reasonable
constant hardness factors for Min Vertex Cover, $\MSAT{2}$, and Max
Cut, and improve the hardness factor for $\MSAT{3}$. We note that our
non-approximability factors for $\maxsnp$ problems are appreciably
close to the values known to be achievable by polynomial time
algorithms. Finally we note a general approach to the derivation of
strong non-approximability results under which the problem reduces to
the construction of certain ``gadgets.''
The increasing strength of non-approximability results via the proof
checking connection motivates us to ask how far this can go, and
whether proofs are inherent in any way. This is addressed in the
second part of the paper. Recall that \cite{fglss} showed how to
translate proof systems for $\NP$ into $\NP$-hardness of approximation
results for Max Clique. We begin with a result of a novel nature
which essentially reverses this connection, showing how any
$\NP$-hardness of approximation result yields a proof system for
$\NP$. Roughly our result says that for any constant $f$ if Max
Clique is $\NP$-hard to approximate within $N^{1/(1+f)}$ then $\NP$ is
in the class $\overline{\fpcp}[\log,f]$ of languages possessing proofs
of logarithmic randomness and amortized free bit complexity $f$. This
indicates that proofs are inherent to obtaining non-approximability
results. But it does more: it provides a tight relation indicating
that to get large hardness factors we must minimize the amortized free
bit complexity. Motivated by this result we look at how low the
amortized free bit complexity can go. We show that a $2$ free bit
complexity is inherent to verifiers constructed using ``current''
recursive proof verification techniques, and thus the long code is
optimal for its use here. In particular, new techniques are required
to prove a better than $N^{1/3}$ factor hardness for Max Clique.
The third part of our paper initiates a systematic investigation of
the properties of PCP and FPCP as a function of the various
parameters: randomness, query complexity, free bit complexity,
amortized free bit complexity, proof size, etc. We are particularly
interested in ``triviality'' results which indicate which combinations
of parameters are ``not'' powerful enough to capture $\NP$. We also
distill the role of randomized reductions in this area, and provide a
variety of useful transformations between proof checking complexity
classes.
