Revision #4 Authors: Mihir Bellare, Oded Goldreich, Madhu Sudan

Accepted on: 18th August 1997 00:00

Downloads: 3081

Keywords:

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.

Revision #3 Authors: Mihir Bellare, Oded Goldreich, Madhu Sudan

Accepted on: 7th December 1996 00:00

Downloads: 3444

Keywords:

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.

Revision #2 Authors: Mihir Bellare, Oded Goldreich, Madhu Sudan

Accepted on: 2nd January 1996 00:00

Downloads: 3845

Keywords:

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.

Revision #1 Authors: Mihir Bellare, Oded Goldreich, Madhu Sudan

Accepted on: 25th September 1995 00:00

Downloads: 2596

Keywords:

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.

TR95-024 Authors: Mihir Bellare, Oded Goldreich, Madhu Sudan

Publication: 26th May 1995 12:20

Downloads: 2058

Keywords:

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.