# «Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

3. Communicating Instances of Hard Problems In this chapter, we investigate a variant of the P vs. NP problem: We model the situation in which a time-bounded agent wants to solve a hard problem and is allowed to communicate with another, arbitrarily powerful agent. The catch is that the second agent does not know the description of the problem yet and can learn about it only by communicating with the ﬁrst agent. We then ask how much communication is required for them to cooperatively solve the problem. Surely, the ﬁrst agent can send the whole problem description so that the second agent can determine the answer. We ﬁnd many problems for which this simple protocol is, in a complexity-theoretically precise sense, likely to be optimal: It is unlikely that they are able to solve the problem by using signiﬁcantly less communication.

3.1. ORs of NP-hard problems All known kernel lower bounds for ﬁxed-parameter tractable problems use – implicitly or explicitly – the fact that compressing ORs of NP-hard problems is impossible under standard complexity-theoretic assumptions. This fact is captured by Lemma 1.1, which we generalize to oracle communication protocols in this section.

Recall that ORt (L) is the problem of deciding whether at least one out of t(s) inputs, each of length s, belongs to L. The following lemma shows that low-cost protocols for ORt (L) can be used to build a proof system with advice for L.

** Lemma 3.1 (Complementary Witness Lemma).**

Let L be a language and t : N → N\{0} be polynomially bounded. If ORt (L) has an oracle communication protocol of cost O(t(s) log t(s)), where the ﬁrst player can be conondeterministic, then L ∈ NP/poly.

** Lemma 1.1 – the incompressibility of ORs of NP-hard problems under coNP ⊆ NP/poly– is a corollary of this lemma.**

To see this, we observe that compressions give rise to lowcost protocols since the ﬁrst player can just compress its input and then send it to the oracle. We now sketch the proof of Lemma 3.1 in the special case where the language L is P-selective. The simpler argument for that case provides a good starting point for the proof of the general case.

A P-selector for a language L is a polynomial-time algorithm that takes two instances x and y as input and outputs one of them, with the guarantee that if at least one of the inputs belongs to L then so does the output. Note that a P-selector for L immediately yields a low-cost oracle communication protocol for deciding OR(L) on inputs consisting of t instances of size s each – the ﬁrst player uses the selector t − 1 times to determine

** **

**3. Communicating Instances of Hard Problems**

which of the instances is “most likely” to be in L, sends that instance to the oracle, who responds with the membership of that instance to L. Since the cost of this protocol is s, any P-selective language satisﬁes the premise of Lemma 3.1 whenever t ≥ s.

Ko [Ko83] showed that the existence of a P-selector for L implies that L (and thus L) can be decided by circuits of polynomial size. The key insight is the following way to prove that an instance x belongs to L: Exhibit an instance y that is known to be in L and which the selector S outputs when given x and y as input. We call such a y a complementary witness. By viewing S on all pairs of a given subset F ⊆ L as a tournament, there always exists a y ∈ F that beats at least half of the x ∈ F and therefore can be used as a proof of membership of x to L. Starting from the set of all instances of size s in L, we repeatedly apply this procedure to the remaining set F of instances that have not yet been beaten by some of the y’s we picked, until the set becomes empty. This way, we obtain a collection As of at most s elements y such that x ∈ L if and only if there exists a y ∈ As such that S(x, y) = y. Using the set As as advice, this shows that L ∈ P/poly. If we allow the selector S to be nondeterministic (even multivalued), we similarly obtain that L ∈ NP/poly [HHN+ 95].

Fortnow and Santhanam [FS08] established the case of Lemma 3.1 where the protocol implements a ≤p -reduction from OR(L) to some language L such that t-tuples consistm ing of instances of bitlength s are mapped to an instance of bitlength bounded by some ﬁxed polynomial in s, independent of t. Their proof can be viewed as an extension of the above argument. The witnesses y are now elements from L, and the requirement on the bitlength of the reduced instances guarantees that suﬃciently popular y’s exist, so we do not need too many of them. The statement of Lemma 3.1 results from a more careful analysis of that argument for size bounds that can grow slowly with t, and from the extension to the general setting of our oracle communication protocols.

Proof (of Lemma 3.1). Let us ﬁrst consider the case of a deterministic oracle communication protocol P modeled by a deterministic polynomial-time Turing machine M and a function f (see §2 for the notation). In this proof we make use of the notion of a communication transcript on a given input x. Such a transcript consists of the sequence of all queries P makes on input x (i.e., the contents of M ’s oracle query tape at the end of the protocol) as well as the answers f (q) to each of the oracle queries q.

The key ingredient of the proof is the following equivalence: An instance x of length s is in L if and only if there exists a sequence x2,..., xt(s) of instances of length s such that P (x, x2,..., xt(s) ) rejects. Here we can view the sequence (x, x2,..., xt(s) ) as an unordered sequence since we can assume w.l.o.g. that P sorts the t instances lexicographically before its actual computation starts. By including a large enough set As of communication transcripts and the value of t(s) as advice, this leads to the following

**proof system with advice for L. On input an instance x of length s:**

2. Check whether there is a communication transcript τ in As that is consistent with P on input (x, x2,..., xt(s) ) and that P (x, x2,..., xt(s) ) rejects. If so, accept;

otherwise, reject.

The check for a given transcript τ involves simulating the ﬁrst player on the input (x, x2,..., xt(s) ). Whenever the ﬁrst player sends a bit to the second player (by writing on the oracle query tape), verify that it agrees with the corresponding bit in τ. Whenever the ﬁrst player expects a bit from the second player (by reading from the oracle answer tape), use the corresponding bit in τ. This process continues until a discrepancy is detected or the ﬁrst player halts.

This proof system is sound as long as all communication transcripts in As are consistent with the protocol P. All that remains to show is the existence of a small subset As of such transcripts that guarantees completeness.

We construct the advice set As for a ﬁxed s in the following greedy way. Consider instances x1,..., xt(s) of L of length s, and let T (x1,..., xt(s) ) denote the communication transcript of P on input (x1,..., xt(s) ). Since the second player is not given the input (x1,..., xt(s) ), the transcript T (x1,..., xt(s) ) is determined solely by the bits sent from the ﬁrst player to the second player. Therefore, the number of distinct such transcripts is less than 2c(s)+1, where c(s) denotes the cost of the protocol on inputs consisting of t(s) instances of length s each. We say that a rejecting transcript τ covers an instance x ∈ L of length s if there exists a sequence x2,..., xt(s) of instances of length s each such that T (x, x2,..., xt(s) ) = τ. We start with As empty and successively pick a rejecting communication transcript τ that covers the largest number of instances x ∈ L of length s that are not covered thus far, and add τ to As. We keep doing so until there are no more instances x ∈ L of length s left to cover.

Consider one step in the construction of As and let F denote the set of uncovered instances x ∈ L of length s at the beginning of the step. Since every tuple in F t(s) is mapped by T to one of the rejecting transcripts above and there are less than 2c(s)+1 distinct such transcripts, there exists a rejecting transcript τ ∗ such that at least a fraction 1/2c(s)+1 of the tuples in F t(s) are mapped by T to this particular τ ∗, i.e., |T −1 (τ ∗ ) ∩ F t(s) | ≥ |F |t(s) /2c(s)+1. Now, each component of each tuple in T −1 (τ ∗ ) ∩ F t(s) is covered by τ ∗ since we can regard the tuples as unordered sequences. Thus, if we let G denote the subset of F that is covered by τ ∗, we have that T −1 (τ ∗ ) ∩ F t(s) ⊆ Gt(s). We conclude that |G|t(s) ≥ |T −1 (τ ∗ ) ∩ F t(s) | ≥ |F |t(s) /2c(s)+1, whence |G| ≥ ϕ(s) · |F | where ϕ(s) = 1/2(c(s)+1)/t(s).

Thus, every step covers a fraction at least ϕ(s) of the remaining instances to be covered.

Since there are at most 2s instances of length s to begin with, after steps there are no more than (1 − ϕ(s)) · 2s ≤ exp(−ϕ(s) ) · 2s instances left to cover, so the process ends after O(s/ϕ(s)) steps. Now, 1/ϕ(s) = 2(c(s)+1)/t(s) is polynomially bounded in t(s) as long as c(s) = O(t(s) log t(s)). Since each transcript as well as the running time of the proof system are polynomially bounded in s and t(s), for polynomially bounded t(s) the resulting algorithm for L runs in NP/poly.

This ﬁnishes the proof for the case of deterministic protocols P. For conondeterministic protocols we can deﬁne T (x1,..., xt(s) ) to be an arbitrary transcript of an execution on which P produces the correct output. The check in step 2 now involves nondeter

<

** **

**3. Communicating Instances of Hard Problems**

minism. The fact that P has no valid rejecting executions for inputs (x1,..., xt(s) ) in OR(L) guarantees the soundness of the proof system, and the existence of at least one valid rejecting execution of P on an input (x1,..., xt(s) ) outside of OR(L) guarantees completeness. The counting argument carries over verbatim.

3.2. Vertex Cover In this section we establish Theorem 1.2 – that d-Vertex Cover has no oracle communication protocol of cost O(nd− ) for any positive constant unless coNP ⊆ NP/poly, where n represents the number of vertices of the d-uniform hypergraph. For ease of exposition we actually develop the equivalent result for d-Clique rather than for d-Vertex Cover. Theorem 1.2 then follows by hypergraph complementation.

We follow the approach outlined in the introduction: We assume that d-Clique has a protocol of low cost and we come up with a suitable reduction from the OR of an NP-hard language L to d-Clique to devise a low-cost protocol for the OR-problem.

We then invoke the complementary witness lemma and obtain that coNP ⊆ NP/poly if the cost of the assumed protocol for d-Clique was too small. The choice of L does not matter, and we pick it to be 3-Sat for convenience. The following lemma provides us with a reduction that is suﬃcient to obtain our tight results.

Before we delve into the proof of this lemma, let us ﬁrst formally derive Theorem 1.2.

** Theorem 1.2 (restated).**

Let d ≥ 2 be an integer and a positive real. If coNP ⊆ NP/poly, there is no protocol of cost O(nd− ) to decide whether a d-uniform hypergraph on n vertices has a vertex cover of at most k vertices, even when the ﬁrst player is conondeterministic.

Proof. Suppose d-Vertex Cover on n-vertex graphs has a protocol of cost O(nc ) for some constant c d. Let L denote 3-Sat. By combining the reduction from Lemma 3.2 with the standard reduction from d-Clique to d-Vertex Cover (mentioned in the preliminaries) and running the above protocol for d-Vertex Cover on the result of the combined reduction, we obtain a protocol for OR(L) of cost O(nc ) = O((s · max(s, t1/d+o(1) ))c ). Since c d the latter expression is O(t(s)) for suﬃciently large polynomials t(s). Lemma 3.1 then shows that 3-Sat is in coNP/poly, which is equivalent to coNP ⊆ NP/poly.

For the reduction in Lemma 3.2, we are given t 3-CNF formulas ϕ1,..., ϕt, and we need to construct a d-uniform hypergraph G on few vertices n and an integer k such that at least one of the ϕi ’s is satisﬁable if and only if G has a clique of size at least k.

We have two independent constructions that achieve an asymptotically optimal bound on the number of vertices n.

** **

**3.2. Vertex Cover**

Elementary Proof We present an elementary reduction from OR(3-Sat) to d-Clique whose basic structure reappears in our lower bounds for packing problems in §3.5. In this reduction we actually achieve a bound of t1/d · poly(s) on the number of vertices, so we do not need to use the additional o(1)-slack in the exponent of t.

Proof (of Lemma 3.2). Let ϕ1,..., ϕt be the t instances of 3-Sat. Without loss of generality, assume that each formula has exactly p = s clauses, each consisting of a sequence of 3 literals. Let P and K1,..., Kt be the hypergraphs provided by Lemma 3.3.

Along the lines of the standard reduction from 3-Sat to 2-Clique by Karp [Kar72], we ﬁrst translate the 3-CNF formulas ϕi into d-uniform hypergraphs Gi on the vertex sets V (Ki ) × [3]. For each i, we identify the elements of V (Ki ) × [3] with (positions of) literals of ϕi : The ﬁrst component selects a clause from ϕi and the second component selects a literal from the clause. We let Gi be the d-uniform hypergraph with as edges all subsets e ⊆ V (Ki ) × [3] of size d such that no two elements of e correspond to the same clause ϕi or represent complementary literals. Note that each such e induces a satisfying assignment of the conjunction of the d clauses touched by e, and that Gi has a clique of size s if and only if ϕi is satisﬁable.

Let G be the union of the Gi ’s, that is, the graph with V (G) = i∈[t] V (Gi ) ⊆ V (P ) × [3] and E(G) = i∈[t] E(Gi ). If ϕi has a satisfying assignment, then Gi has a clique of size s and so has G. For the other direction, let K be a clique of size s in G. The projection K of K onto the ﬁrst component is a clique of size s in P. By property (ii) of Lemma 3.3, K = Ki for some i ∈ [t]. Moreover, by property (i) of Lemma 3.3, the projections of E(Gi ) and E(Gj ) for j = i are disjoint. It follows that K is a clique of size s in Gi, and therefore ϕi is satisﬁable.