On Approximating NP-Hard Optimization Problems

Johan Håstad

Abstract. We discuss the efficient approximability of NP-hard optimization problems. Although the methods apply to several problems we concentrate on the problem of satisfying the maximal number of equations in an over-determined system of linear equations. We show that over the field of two elements it is NP-hard to approximate this problem within a factor smaller than 2. The result extends to any Abelian group with the size of group replacing the constant 2. 1991 Mathematics Subject Classification: 68Q25,68Q99 Keywords and Phrases: Approximation algorithms, NP-hard optimization problems, Linear equations

1 Introduction

The basic entity in complexity theory is a computational problem which, from a mathematical point of view, is simply a function F from finite binary strings to finite binary strings. To make some functions more intuitive these finite binary strings should sometimes be interpreted as integers, graphs, or descriptions of polynomials. An important special case is given by decision problems where the range consists of only two strings, usually taken to be 0 or 1.

The basic notion of efficiently computable is defined as computable in time polynomial in the input-length. The class of polynomial time solvable decision problems is denoted by P. Establishing that a problem cannot be solved efficiently can sometimes be done but for many naturally occurring computational problems of combinatorial nature, no such bounds are known. Many such problems fall into the class NP; problems where positive answers have proofs that can be verified efficiently. The standard problem in NP is satisfiability (denoted SAT), i.e. the problem of given a Boolean formula φ over Boolean variables, is it possible to assign truth values to the variables to make φ true? The most common version of SAT, which is also the one we use here, is to assume that φ is a CNF-formula, i.e. a conjunction of disjunctions.

It is still unknown whether NP=P, although it is widely believed that this is not the case. It is even the case that much work in complexity theory, and indeed this paper, would have to be completely reevaluated if it turns out that NP=P. There is a group of problem, called the NP-complete problems, introduced by Cook [8], which have the property that they belong to P iff NP=P. Thus being NP-complete is strong evidence that a problem is computationally intractable and literally thousands of natural computational problems are today known to be NPcomplete (for an outdated but still large list of hundreds of natural problems see [13]). SAT is the most well known NP-complete problem.

Many combinatorial optimization problems have a corresponding decision problem which is NP-complete. As an example take the traveling salesman problem of finding the shortest tour that visits a certain set of cities. The corresponding decision problem, namely that of, given K, determine if there is a tour of length K is NP-complete and thus solving the optimization problem exactly in polynomial time would mean that NP=P. Optimization problem with this property are called NP-hard (not NP-complete as they do not fall into the class NP as they are not decision problems). Solving NP-hard optimization problems exactly is thus hard, but in many practical circumstances it is almost as good to get an approximation of the optimum. Different NP-hard optimization problems behave very differently with respect to efficient approximation algorithms and this set of questions has lead to many interesting results.

The goal of this paper is to derive lower bounds on how well natural optimization problems can be approximated efficiently. The type of result we are interested in is a conclusion of the form ”If optimization problem X and be approximated within factor c in polynomial time, then NP=P”. The techniques we discuss give results for many optimization problem but we here concentrate on solving overdetermined systems of linear equations over finite Abelian groups. For this problem we are given a set of m equations in n unknowns and the task is to determine the maximal number of equations that can be simultaneously satisfied and possibly also produce an assignment that satisfies this number of equations.

An algorithm is a c-approximation algorithm if it, for every instance, finds a solution that is within a factor c of the optimal value. Thus if the best assignment satisfies o equation, such an approximation algorithm would always find an assignment that satisfies o/c equations. For linear equations over GF[2] a random assignment satisfies, on the average, half the equations. It is hence not surprising that one can efficiently find an assignment that satisfies at least half the equations. This gives a 2-approximation algorithm and the result extends to any Abelian group G to give a size(G)-approximation algorithm. The main result we discuss in this paper is to prove that this simple heuristic is optimal in that for any Abelian group G and any ϵ > 0 it is NP-hard to size(G) − ϵ-approximate the problem of linear equations over G.

The main tool for deriving such strong approximability results was introduced in the seminal paper [10]. It gives a connection to multiprover interactive proofs and let us here give an informal description of a variant of this concept. We later give some formal definitions in Section 1.1.

NP can be viewed as a proof system where a single prover P tries to convince a polynomial time verifier V that a statement is true. For concreteness let us assume that the statement is that a formula φ is satisfiable. In this case, P displays a satisfying assignment and V can easily check that it is a correct proof. This proof system is complete since every satisfiable φ admits a correct proof, and it is sound since V can never be made to accept an incorrect statement.

If φ contains n variables, V reads n bits in the above proof. Suppose we limit V to reading fewer bits where the most extreme case would be to let this number be constant independent of the the number of variables in φ. It is not hard to see that the latter is impossible unless we relax the requirements of the proof. The proof remains a finite binary string, but we allow the verifier to make random choices. This means that given φ we should now speak of the probability that V accepts a certain proof π. Soundness is relaxed in that when φ is not satisfiable then there is some constant s < 1 such that for any proof π the probability that V accepts is bounded by s. A bit surprisingly it turns out that it is convenient also to relax completeness in that we only require the verifier to accept a correct proof for a correct statement with probability c > s where we might have c < 1. Note that both completeness and soundness probabilities are taken only over V ’s internal random choices and hence we can improve these parameters by making several independent verifications and taking a majority decision. Naturally this increases other parameters that we want to keep small such as the number of bits of the proof that V reads.

It is an amazing fact, proved by Arora et al [1], that any NP-statement has a proof of the above type, usually called probabilistically checkable proof or simply PCP, where V only reads a constant, independent of the size of the statement being verified, number of bits of the proof and achieves soundness s = 1/2 and completeness c = 1. Apart from being an amazing proof system this gives a connection to approximation of optimization problems as follows.

Fix a formula φ and consider the PCP by Arora et al. Since everything is fixed except the proof π, we have a well defined function acc(π), the probability that V accepts a certain proof π. Consider max_{π} acc(π). If φ is satisfiable then this optimum is 1, while if φ is not satisfiable then the optimum is ≤ s. Thus, even computing this optimum approximately would enable us to decide an NP-complete question. Now by choosing the test appropriately this optimization problem can be transformed to more standard optimization problems leading to the desired inapproximability results.

1.1 Probabilistic proof systems

As discussed in the introduction we are interested in proof systems where the verifier is a probabilistic Turing machine. The simplest variant is a probabilistically checkable proof.

Definition 1.1 A Probabilistically Checkable Proof (PCP) with completeness c and soundness s for a language L is given by a verifier V such that for x ∈ L there is a proof π such that V^{π} outputs 1 on input x with probability at least c, and for x ∉ L and all π the probability that V^{π} outputs 1 on input x is bounded by s.

We are interested in efficient PCPs and hence we assume that V runs in worst case polynomial time. It is also important for us to efficiently enumerate all the random choice of V and hence we need that V only makes O(log |x|) binary random choices on input x. We maintain this property without mentioning it explicitly.

We also need what is generally called a two-prover one-round interactive proof. Such a verifier has two oracles but has the limitation that it can only ask one question to each oracle and that both questions have to be produced before either of them is answered. We do not limit the answer size of the oracles. We call the two oracles P_{1} and P_{2}.

Definition 1.2 A probabilistic polynomial time Turing machine V is a verifier in a two-prover one-round proof system with completeness c and soundness s for a language L if on input x it produces two strings q_{1}(x) and q_{2}(x), such that for x ∈ L there are two oracles P_{1} and P_{2} such that the probability that V accepts (x, P_{1}(q_{1}(x)), P_{2}(q_{2}(x))) is c while for x ∉ L, for any two oracles P_{1} and P_{2} the probability that V accepts (x, P_{1}(q_{1}(x)), P_{2}(q_{2}(x))) is bounded by s.

In all our two-prover interactive proofs the verifier always accepts a correct proof for a correct statement, i.e. we have c = 1 in the above definition.

Brief history. The notion of PCP was introduced by Arora and Safra [2]. It was a variation of randomized oracle machines discussed by Fortnow et al [12] and transparent proofs by Babai et al [4]. Multiprover interactive proofs were introduced by Ben-Or et al [7], and all these systems are variants of interactive proofs as introduced by Goldwasser, Micali, and Rackoff [14] and Babai [3].

1.2 Essential previous work

The surprising power of interactive proofs was first established in the case of one prover [17], [20] and then for many provers [5]. After the fundamental connection with approximation was discovered [10] the parameters of the proofs improved, culminating in the result [2, 1] that it is sufficient to read a constant number of bits. Using a transformation of [18] and massaging the result slightly we arrive at the following theorem.

Theorem 1.3 [1] Let L be a language in NP and x be a string. There is a universal constant c < 1 such that, we can in time polynomial in size(x) produce a CNF formula φ_{x,L} with exactly 3 literals in each clause such that if x ∈ L then φ_{x,L} is satisfiable while if x ∉ L, any assignment satisfies at most a fraction c of the clauses of φ_{x,L}. Furthermore, we can assume that each variable appears exactly 12 times.

Let us now turn to two-prover interactive proofs. Given a one-round protocol with soundness s and completeness 1 we can repeat it k times in sequence improving the soundness to s^{k}. This creates a many round protocols, whereas we need our protocols to remain one-round. This can be done by parallel repetition in that V repeats his random choices to choose k pairs of questions (q_{1}^{(i)}, q_{2}^{(i)})_{i=1}^{k} and sends (q_{1}^{(i)})_{i=1}^{k} to P_{1} and (q_{2}^{(i)})_{i=1}^{k} to P_{2} all at once. V then receives k answers from each prover and accepts if it would have accepted in all k protocols given each individual answer. The soundness of such a protocol can be greater than s^{k}, but Raz [19] proved that when the answer size is small the soundness is exponentially decreasing with k.

Theorem 1.4 [19] For all integers d and s < 1, there exists c_{d,s} < 1 such that given a two-prover one-round proof system with soundness s and answer sizes bounded by d, then for all integers k the soundness of k protocols run in parallel is bounded above by c_{d,s}^{k}.

1.3 Definitions for approximation algorithms

Definition 1.5 Let O be a maximization problem. For an instance x of O let OP T (x) be the optimal value. An efficient C-approximation algorithm is an algorithm that on any input x outputs a number V such that OP T (x)/C ≤ V ≤ OP T (x) and runs in worst case polynomial time.

2 First steps towards a good proof system

We want to construct a proof system for an arbitrary language in NP and let us start by an overview.

We start by a simple two-prover one-round protocol which is obtained more or less immediately from Theorem 1.3. We improve the soundness of this protocol by running several copies of it in parallel and using Theorem 1.4. It is possible to transform this improved two-prover protocol to a PCP simply by writing down the prover answers. The answers are, however, long and since we want to keep the number of read bits very small we write the answers in a more useful form by asking the prover to supply the value of all Boolean functions of these answers. This is the long code of the answers as defined in [6]. We now proceed to give the details.

Suppose φ = C_{1} ∧ C_{2} ∧ … ∧ C_{m}, where C_{j} contains the variables x_{a_{j}}, x_{b_{j}} and x_{c_{j}}. Consider the following one-round two-prover interactive proof.

Simple two-prover protocol

1. V chooses j ∈ [m] and k ∈ {a_{j}, b_{j}, c_{j}} both uniformly at random. V sends j to P_{1} and k to P_{2}.

2. V receives values for x_{a_{j}}, x_{b_{j}} and x_{c_{j}} from P_{1} and for x_{k} from P_{2}. V accepts if the two values for x_{k} agree and C_{j} is satisfied.

We have the following proposition which can be proved by a straightforward argument which we omit.

Proposition 2.1 If any assignment satisfies at most a fraction e of the clauses of φ, then V accepts in the simple two prover protocol with probability at most (2 + e)/3.

We now concentrate a protocol we called the u-parallel 2-prover game and which consists of u copies of this basic game. That is, the verifier picks u clauses (C_{j_{k}})_{k=1}^{u} and then uniformly at random for each k he picks a random variable x_{i_{k}} contained in C_{j_{k}}. The variables of (C_{j_{k}})_{k=1}^{u} are sent to P_{1} while (x_{i_{k}})_{k=1}^{u} are sent to P_{2}. The two provers respond with assignments on the queried variables and the verifier checks that the values are consistent and that the chosen clauses are satisfied. We get completeness 1 and the soundness is in the case of φ_{x,L} of Theorem 1.3 is, by Theorem 1.4 and Proposition 2.1, bounded by c_{1}^{u} for some constant c_{1} < 1. To fix notation, Let U = {x_{i_{1}}, x_{i_{2}} … x_{i_{u}}} be the set of variables sent to P_{2}, and W the set of variables sent to P_{1}.

As discussed in the introduction to this section we want to replace this twoprover interactive proof by a PCP consisting of the answers of P_{1} and P_{2} given in a more redundant form. We use the powerful long code introduced in [6].

Definition 2.2 The long code of a string x of length w is of length 2^{2^{w}}. The coordinates of the codeword are identified with all possible functions f : {0, 1}^{w} ↦ {0, 1} and the value of coordinate f is f(x).

Before we continue, let us fix some more notation. The written part of the PCP described above is called a Standard Written Proof of size u or simply SWP(u). Let F_{T} denote the set of functions on a set T and let A_{T} be the supposed long code of the restriction of the satisfying assignment to the set T. It is convenient to have {−1, 1} as our set of two values for Boolean functions and Boolean variables and thus exclusive-or turns into multiplication. For the supposed long code A_{T} we assume that A_{T} (f) = −A_{T} (−f). This is achieved by, for each pair (f, −f), having only one value in A_{T}. This value is negated if the value of A_{T} (−f) is needed. For the tables A_{W}, we know that it should be a long code for some assignment that satisfies ∧_{k}C_{j_{k}} and instead of storing an entry for each g ∈ F_{W} we only store an entry for each function of the form g ∧ (∧_{k}C_{j_{k}}). When we want the value of a function h we access the entry for h ∧ (∧_{k}C_{j_{k}}). A SWP(u) is correct for φ if there is an assignment x that satisfies φ and thus that A_{T} (f) = f(x|_{T}) for any supposed long code A_{T} for any set T obtained as U or W in a run of the u-parallel 2-prover game.

We need the discrete Fourier transform defined by

Â_{α,T} = 2^{−2^{size(T)}} ∑_{f} A_{T} (f) ∏_{x∈α} f(x)

for any α ⊆ {−1, 1}^{T}. It is inverted by

A_{T} (f) = ∑_{α} Â_{α,T} ∏_{x∈α} f(x).

and since |A(f)| = 1 for any f we have, by Parseval’s identity, ∑_{α} Â_{α,T}^{2} = 1. For a set β ⊆ {−1, 1}^{W} and U ⊂ W we let π_{2}^{U}(β) ⊆ {−1, 1}^{U} be those elements that have an odd number of extensions in β. This a mod 2 projection and note that it might be empty even if β is not empty.

3 Linear equations

We now study the optimization problem of satisfying the maximal number of equations mod 2. For natural reasons we want to design a test for SWP(u) that accepts depending only on the exclusive-or of three bits of the proof.

Test L_{2}^{ϵ}(u)

Written proof. A SWP(u).

Desired property. To check that it is a correct SWP(u) for a given formula φ = C_{1} ∧ C_{2} … C_{m}. Verifier. Choose set U and W as in the u-parallel 2-prover game. Choose f ∈ F_{U} and g_{1} ∈ F_{W} with the uniform probability. Choose a function μ ∈ F_{W} by setting μ(y) = 1 with probability 1−ϵ and μ(y) = −1 otherwise, independently for each y ∈ {−1, 1}^{W}. Define g_{2} by for each y ∈ {−1, 1}^{W}, g_{2}(y) = f(y|_{U})g_{1}(y)μ(y). Accept if A_{U}(f)A_{W} (g_{1})A_{W} (g_{2}) = 1.

We need to analyze the soundness and completeness of this test.

Lemma 3.1 The completeness of Test L_{2}^{ϵ}(u) is at least 1 − ϵ.

Proof: Fix a correct SWP(u) obtained from the assignment x satisfying φ We claim that V accepts unless μ(x|_{W}) = −1 and leave the verification to the reader.

Lemma 3.2 For any ϵ > 0, δ > 0, suppose that the probability that the verifier of Test L_{2}^{ϵ}(u) accepts is (1 + δ)/2. Then there is a strategy for P_{1} and P_{2} in the u-parallel two prover protocol that makes the verifier of that protocol accept with probability at least ϵδ^{2}/2.

Proof: Let us first fix U and W and for notational convenience we denote the function A_{U} by A and the function A_{W} by B. We want to consider

E_{f,g_{1},μ}[A(f)B(g_{1})B(g_{2})]  (1)

since by the assumption of the lemma

E_{U,W,f,g_{1},μ}[A_{U}(f)A_{W} (g_{1})A_{W} (g_{2})] = δ.  (2)

Using the Fourier expansion and moving the expected value inside (1) equals

∑_{α,β_{1},β_{2}} Â_{α}B̂_{β_{1}} B̂_{β_{2}}E_{f,g_{1},μ} [∏_{x∈α} f(x) ∏_{y∈β_{1}} g_{1}(y) ∏_{y∈β_{2}}(f(y|_{U})g_{1}(y)μ(y))] .  (3)

If β_{1} ≠ β_{2} then since g_{1}(y) for y ∈ β_{1}Δβ_{2} is random and independent of all other variables the inner expected value in this case is 0 and thus we can disregard all terms except those with β_{1} = β_{2} = β. Now consider such a term and let s_{x} be number of y ∈ β such that y|_{U} = x. Since f(x) is random and independent for different x, unless for every x either x ∈ α and s_{x} is odd or x ∉ α and s_{x} is even again the inner expected value is 0. These conditions imply that we only keep terms with π_{2}^{U}(β) = α and finally since E_{μ}[∏_{y∈β} μ(y)] = (1 − 2ϵ)^{size(β)} we have reduced the sum (1) to

∑_{α} ∑_{β|π_{2}^{U} (β)=α} Â_{α}B̂_{β}^{2}(1 − 2ϵ)^{size(β)}.  (4)

We want to prove that if the expected value of this (over random choices of U and W) is at least δ then we have a good strategy of the provers. We define good randomized strategies for P_{1} and P_{2}.

The strategy of P_{2} is first to pick a random α with and Â_{α} ≥ δ/2. The probability of picking α is defined to be proportional to Â_{α} and hence by Parseval’s identity it is at least δÂ_{α}/2. P_{2} sends a random x ∈ α. Note that α is nonempty since A_{U}(f) = −A_{U}(−f) implies that Â_{∅} = 0.

The strategy of P_{1} is to pick a random β with probability B̂_{β}^{2} and then answer with a random y ∈ β.

Let us evaluate the success-rate of this strategy. By the property that A_{W} (h) only depends on h ∧ (∧_{k}C_{j_{k}}) it is not hard to establish that every y sent by P_{1} satisfies the corresponding clauses and thus we only need to look at the probability that the answers are consistent. This probability is at least size(β)^{−1} times the probability that for the picked α and β we have α = π_{2}^{U}(β). The probability of picking a specific pair α and β is, provided Â_{α} > δ/2, at least Â_{α}B̂_{β}^{2}δ/2 and thus the overall success-rate for a fixed choice of U and W is at least

δ/2 ∑_{α|Â_{α}|≥δ/2} ∑_{β|π_{2}^{U} (β)=α} Â_{α}B̂_{β}^{2}size(β)^{−1}.  (5)

Comparing this sum to (4) and making some calculations one can establish that expected value over U and W is at least δ^{2}ϵ/2 and the proof of Lemma 3.2 is complete.

Armed with the very efficient PCP given by Test L_{2}^{ϵ}(u) we can now establish the main theorem of this paper.

Theorem 3.3 For any ϵ > 0 it is NP-hard to approximate the problem of maximizing the number of satisfied equation in a system of linear equations mod 2 within a factor 2 − ϵ. The result applies to systems with only 3 variables in each equation.

Proof: (Sketch) Let L be an arbitrary language in NP and given an input x, create the formula φ_{x,L} as given in Theorem 1.3. Let δ be small positive number to be determined and consider test L_{2}^{δ}(u) where u is chosen sufficiently large so that the acceptance probability in the u-parallel 2-prover game is smaller than δ^{3}/2.

For each bit b in a SWP(u) introduce a variable x_{b}. To accept in the test L_{2}^{δ}(u) is equivalent to the condition

b_{U,f}b_{W,g_{1}}b_{W,g_{2}} = c

where b_{U,f}, b_{W,g_{1}} and b_{W,g_{2}} are the bits in the proof corresponding to A_{U}(f), A_{W} (g_{1}) and A_{W} (g_{2}), respectively^{1}. Write down the equation

x_{b_{U,f}} x_{b_{W,g_{1}}} x_{b_{W,g_{2}}} = c

1One might think that the right hand size would always be 1, but because of our convention on having one entry in A_{U} to represent the value on two functions this might be the case since the value corresponding to A_{U} (f) in the proof might actually give the value of A_{U} (−f)

Documenta Mathematica · Extra Volume ICM 1998 · III · 441–450

with a weight that is equal to the probability that the verifier chooses the tuple (U, W, f, g_{1}, g_{2}). Now each proof corresponds to an assignment to the variables x_{b} and the total weight of all satisfied equations is exactly the probability that this proof is accepted. This implies that if x ∈ L this maximal weight is 1 − δ while if x ∉ L, it is, in view of Lemma 3.2 and the choice of u, at most (1 + δ)/2. It is not difficult to check that we have a polynomial number of equations and an approximation algorithm with performance ratio smaller than 2 − ϵ would enable us, for sufficiently small δ, to answer a NP-hard question.

As is standard, the weights can be eliminated by duplicating each equation a suitable number of times. This creates a slight degrade in the value of ϵ, but since ϵ is arbitrary anyway this can easily be compensated. We omit the details.

Note that there is a meta reason that we have to introduce the error function μ and make our test have non perfect completeness. If we had perfect completeness then the equations produced in the proof of Theorem 3.3 could all be satisfied simultaneously. However, to decide if a set of linear equations have a common solution can be done in polynomial time by Gaussian elimination.

Finally, let us just state the extension to an arbitrary Abelian group.

Theorem 3.4 For any ϵ > 0 and any Abelian group G, given a system of linear equations over G, it is NP-hard to approximate the maximal number of simultaneously satisfiable equations within a factor size(G) − ϵ. The result applies to systems with only 3 variables in each equation.

4 Final remarks

As mentioned in the introduction the efficient multiprover interactive proofs give strong inapproximability results for many combinatorial optimization problems.

Independence number is to, given a graph G, find the largest set S of nodes such that no two nodes in S ares pairwise connected. It is established in [15] that it is, assuming that NP cannot be done in probabilistic polynomial time, for any ϵ > 0, hard to approximate independence number within n^{1−ϵ} where n is the number of nodes G. A very related problem is that of chromatic number where we want to color the nodes in G with the minimal number of colors so that adjacent nodes get different colors. The result for independence number can be extended to chromatic number [11]. The problem of set cover is that given a number of subsets S_{i} of [n] to find the minimal size sub-collection of the S_{i} that covers the entire set. This problem is, under standard complexity assumptions, hard to approximate within (1 + o(1)) ln n [9] and this result is tight. For inapproximability results on other problem, some optimal and some non-optimal we refer to the full versions of [6] and [16].

References

[1] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and intractability of approximation problems. Proc. of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 1992, pp 14-23.

450 Johan Håstad

[2] S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, Vol 45, 1998, pp 70-122.

[3] L. Babai. Trading group theory for randomness. Proc. of the 17th Annual ACM Symposium on Theory of Computation, Providence, 1985, pp 420-429.

[4] L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polynomial time. Proc. of the 23rd Annual ACM Symposium on Theory of Computation, New Orleans, 1991, pp 21-31.

[5] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, Vol 1, 1991, pp 3-40.

[6] M. Bellare, O. Goldreich and M. Sudan. Free Bits, PCPs and Non-Approximability-Towards tight Results. Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, Milwaukee, pp 422-431. Full version available from ECCC, Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc).

[7] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multiprover interactive proofs. How to remove intractability. Proc. of the 20th Annual ACM Symposium on Theory of Computation, Chicago, 1988, pp 113-131.

[8] S. A. Cook. The complexity of Theorem Proving Procedure. Proceeding 3rd ACM Symposium on Theory of Computing, 1971, pp 151-158.

[9] U. Feige. A threshold of ln n for approximating set cover. Proc. of the 28th Annual ACM Symposium on Theory of Computation, Philadelphia 1996, pp 314-318.

[10] U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, Vol, 43:2, pp 268-292.

[11] U. Feige and J. Kilian. Zero-Knowledge and the chromatic number. Proc. of the 11th Annual IEEE conference on Computational Complexity, Philadelphia 1996, pp 278-287.

[12] L. Fortnow, J. Rompel, and M. Sipser. On the power of Multi-Prover Interactive Protocols. Proc. 3rd IEEE Symposium on Structure in Complexity Theory, pp 156-161, 1988.

[13] M.R. Garey and D.S. Johnsson. Computers and Intractability. W.H. Freeman and Company, 1979.

[14] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, Vol 18, pages 186-208, 1989.

[15] J. Håstad. Clique is hard to approximate within n^{1−ϵ}. Proc. of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington 1996, pp 627-636. Full version available from ECCC, Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc).

[16] J. Håstad. Some Optimal In-approximability Results. Proc. 29th Annual ACM Symposium on Theory of Computation, 1997, pp 1-10. Full version available from ECCC, Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc).

[17] C. Lund, L. Fortnow, H. Karloff and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, Vol 39, No 2, pp 859-868.

[18] C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, Vol 43, 1991, pp 425-440.

[19] R. Raz. A parallel repetition theorem. Proc. of the 27th Annual ACM Symposium on Theory of Computation, Las Vegas 1995, pp 447-456.

[20] A. Shamir. IP=PSPACE. Journal of the ACM, Vol 39, No 2, pp 869-877.

Johan Håstad

Dept of Numerical Analysis and Computing Science Royal Institute of Technology S-100 44 Stockholm Sweden