Hardness of Approximation Between P and NP. Aviad Rubinstein

Hardness of Approximation Between P and NP

(w_[1,k], v_[k+1,n]) denotes the vector with the first k coordinates as in w and the last n − k coordinates as in v.

The information of a single query of QUERY END-OF-THE-LINE (for the above class of lines) can be extracted from π(i − 1), π(i), and π(i + 1). Therefore QUERY END-OF-THE-LINE is at least as hard as the problem of finding the first bit of the last element in a random permutation, where each query returns the previous, the current, and the next vertices. Conditioning on the answers to k queries π(q₁ − 1), π(q₁), π(q₁ + 1),…, π(qk − 1), π(qk), π(qk + 1), the last element of the permutation is still uniformly random across all vertices that are not π(q₁),…, π(qk), π(q₁ − 1),…, π(qk − 1), π(q₁ + 1),…,π(qk + 1). This proves that the latter problem requires Ω(2ⁿ) queries.

3.5.2 Communicationally Hard, Discrete End-of-Any-Line Problem

In order to use a simulation theorem (Theorem 2.5) for randomized communication complexity, we define the following simulation variant of QUERY END-OF-THE-LINE:

Definition 3.2

SIMULATION END-OF-THE-LINE. We let N = 2ⁿ·2ⁿ·(n + 1)·3.

Input: For each v ∈{0, 1}ⁿ ×{0, 1}ⁿ × [n + 1], Alice receives three vectors , and Bob receives three indices .

We define

We simulate the problem QUERY END-OF-THE-LINE; therefore we restrict attention to inputs such that (T, S, P) that are defined in (3.1) meet all the requirements of QUERY END-OF-THE-LINE.

Output: The first bit ([v*]₁) of a non-trivial end or start of a line (v*, v*, 0) ≠ 0_2n+1.

Applying the randomized simulation theorem (Theorem 2.5) to the query complexity lower bound (Lemma 3.2) gives a lower bound on the randomized communication complexity of a discrete end-of-line problem SIMULATIONEND-OF-THE-LINE.

Corollary 3.4

(SIMULATIONEND-OF-THE-LINE) = Ω(2ⁿ).

3.5.3 Embedding a Line as a Local Lipschitz Function

We embed I as a Euclidean-norm hard continuous function à la Section 4.2. Below, we recall some of the properties of the construction that will be useful for our reduction.

It will be more convenient to think of G as a graph over {0, 1}²ⁿ+^log(n+1).

Let m =Θ(2n+ log(n + 1)) = Θ(n) and let E: {0, 1}^2n+log(n+1) → {0, 1}^m denote the encoding function of a good binary error-correcting code. We embed the discrete graph G into the continuous cube [−1, 2]^4m.

The vertex v is embedded to the point (E(v), E(v), 0m, 0_m) ∈ [−1, 2]^4m, which is called the embedded vertex.

For two vertices v, w ∈ V such that (v, w) is an edge in the graph G, we define five vertices:

Note that x¹(v, w) is the embedded vertex v, x⁵(v, w) is the embedded vertex w.

The line that connects the points xⁱ(v, w) and xⁱ⁺¹(v, w) is called a Brouwer line segment. The union of these four Brouwer line segments is called the embedded edge (v, w). It is not hard to check that non-consecutive Brouwer line segments are Ω(1)-far one from the other, and in particular it implies that non-consecutive embedded edges are sufficiently far one from the other.

The following proposition shows that the END-OF-THE-LINE problem can be reduced to the problem of finding an approximate fixed point of a continuous Lipschitz function, when the function is “local” in the following sense: every edge in G is embedded as a path in the continuous hypercube (as described above). For points close to the embedding of an edge, f depends only on the “local behavior” of the lines I at the endpoints of this edge; for all other points, f is independent of the lines I.

Proposition 3.1

Theorem 4.2 and Fact 4.2. There exist constants δ, h> 0 such that given a line I = (T, S, P) over G there exists a function f = f(I) = [−1, 2]^4m → [−1, 2]^4m with the following properties:

1. ||f(x) − x||₂ >δ for every x that is not h-close to the embedded edge of the end of the line (i.e., the embedding of the edge (P(v*), v*).

2. f is 0(1)-Lipschitz in ||·||₂ norm.

3. f is local in the sense that it can be defined as an interpolation between a few (in fact, 64) functions, , that do not depend on the lines I and such that:

(a) If the first m-tuple of coordinates of x is 6h-close to the encoded vertex E(v), but the second m-tuple of coordinates of x is 6h-far from any encoded vertex E(w), then for every I₂ ∈ {0, 1}³.

(b) If the second m-tuple of coordinates of x is 6h-close to the encoded vertex E(w), but the first m-tuple of coordinates of x is 6h-far from any encoded vertex E(v), then for every I₁ ∈ {0, 1}³.

(c) If the first m-tuple of coordinates of x is 6h-close to the encoded vertex E(v), and the second m-tuple of coordinates of x is 6h-close to the encoded vertex E(w), then f_(I(v),I(w)(x) = f(x).

(d) If none of the above conditions are satisfied, then for every I₁, I₂ ∈ {0, 1}³.

3.5.4 Two-Player Game

Theorem 3.3

Theorem 3.1, restated.

Скачать книгу