Эротические рассказы

Hardness of Approximation Between P and NP. Aviad RubinsteinЧитать онлайн книгу.

Hardness of Approximation Between P and NP - Aviad Rubinstein


Скачать книгу
alt="image"/> is

image

      where [·]ϵ denotes the rounding to the closest ϵ integer multiplication. x* yields a payoff of at least

image

      Note that in every ϵ4-ANE Alice assigns a probability of at most 1 − ϵ2 to actions that are ϵ2-far from optimal. By Equation (3.2) this implies that the probability that Alice choosing a vector x that satisfies image is at most ϵ2.

      ■

      In every ϵ4-ANE image, if the first m-tuple of coordinates of image is 6h-close to the binary encoding E(v) of a vertex v, then

      with probability of at least 1 − O(ϵ4) (where the probability is taken over image).

       Proof

      By Lemma 3.3 and the triangle inequality, with probability of at least 1 − ϵ2, the first m-tuple of x is O(h)-close to E(v). Rounding to Rv(x) ∈ {0, 1}m can at most double the distance to E(v) in each coordinate. Therefore, the Hamming distance of Rv(x) and E(v) is O(h). Hence Rv(x) is correctly decoded as Dv(x) = v, with probability of at least 1 − ϵ2.

      Since image do not affect image, Bob’s utility from guessing vB = v, and image, is at least 1 − ϵ2, whereas his utility from guessing any other guess is at most ϵ2. Therefore, Bob assigns probability at least 1 − ϵ4/(1 − 2ϵ2) to actions that satisfy (3.3).

      ■

      A similar lemma holds for the second m-tuple of x and the vertex w:

       Lemma 3.5

      In every ϵ4-ANE image, if the second m-tuple of coordinates of image is 6h-close to the binary encoding E(w) of a vertex w, then

image

      with probability of at least 1 − O(ϵ4) (where the probability is taken over image).

      Since Alice receives the correct vB and βB, we also have:

      In every ϵ4-ANE image, if the first m-tuple of coordinates of image is 6h-close to the binary encoding E(v) of a vertex v, then

image

      with probability 1 − O(ϵ4) (where the probability is taken over image and image).

       Proof

      Follows immediately from Lemma 3.4 and the fact that image does not affect image

      ■

      A similar lemma holds for the second m-tuple of x and the vertex w:

      In every ϵ4-ANE image, if the second m-tuple of coordinates of image is 6h-close to the binary encoding E(w) of a vertex w, then

image

      with probability 1 − O(ϵ4) (where the probability is taken over image and image).

      In every ϵ4-ANE image with probability 1 − O(ϵ4).

       Proof

      Follows immediately from Lemmas 3.6 and 3.7 and the “locality” condition in Proposition 3.1.

      ■

      The following corollary completes the analysis of the 2-player game.

      In every ϵ4-ANE image.

       Proof

      We recall that in Lemma 3.3 we have proved that

      with probability 1 − O(ϵ4). This also implies that x is, with high probability, close to its expectation:

Яндекс.Метрика