Hardness of Approximation Between P and NP. Aviad Rubinstein
Definition 2.5
END-OF-A-LINE. The input to the problem is functions S, P : {0, 1}n → {0, 1}n, such that S(0n) = 0n ≠ P(0n). The output is another odd-degree vertex 0n ≠ v ∈ {0, 1}n such that P(S(v)) ≠ S(P(v)).
The computational complexity class PPAD is defined as the class of all total search problems reducible to END-OF-A-LINE.
MEMBERSHIP END-OF-A-LINE
The following variant of END-OF-A-LINE is equivalent and more convenient for some of our reductions. In particular, the problem is restricted to a subset of the vertices. The restricted vertex-set is defined implicitly via a membership function T : {0, 1}n → {0, 1}. Abusing notation, let T also denote the restricted set of vertices whose T-value is 1. We think of S and P as only applying to vertices in T, and connecting them to other vertices in T. Formally, we also allow the algorithm to return any violations.
Definition 2.6
MEMBERSHIP END-OF-A-LINE. The input to the problem is functions S, P : {0, 1}n → {0, 1}n and T : {0, 1}n → {0, 1}, such that S(0n) = 0n ≠ P(0n) and T(0n), T(S(0n)) = 1. The output is another odd-degree vertex 0n ≠ v ∈ {0, 1}n such that T(v) = 1 and v satisfies at least one of the following:
End-of-a-line. P(S(v)) = S(P(v));or
Boundary condition. T(S(v)) = 0 or T(P(v)) = 0.
Lemma 2.1
END-OF-A-LINE is equivalent to MEMBERSHIP END-OF-A-LINE.
Proof
Given an instance of END-OF-A-LINE, we can construct an equivalent instance of MEMBERSHIP END-OF-A-LINE by setting T ≡ 1. In the other direction, we can add self-loops to every vertex v such that T(v) = 0 (i.e., P(v) = S(v) = v); this guarantees that v is never a solution to the new END-OF-A-LINE instance.
■
We will be interested in restricted (but equally hard) variants of MEMBERSHIP END-OF-A-LINE. For example, in Section 16.2 we define LOCAL END-OF-A-LINE where, among other restrictions, T, S, P are AC0 circuits. In particular, in Chapter 3, we will consider a variant where each vertex is a priori restricted to have at most two potential incoming/outgoing neighbors, and the functions S, P merely specify which neighbor is chosen. We then abuse notation and let S, P output just a single bit.
2.3 Exponential Time Hypotheses
Our quasi-polynomial hardness results are conditional on the following hypotheses. We begin with the “plain” ETH:
Hypothesis 2.1
Exponential time hypothesis (ETH) [Impagliazzo et al. 2001]. 3SAT takes time 2Ω (n).
Since a Nash equilibrium always exists, we are unlikely to have a reduction (even of subexponential size) from 3SAT to Nash equilibrium. Instead, we need to assume the following analogue of ETH for the total class PPAD:
Hypothesis 2.2
ETH for PPAD [Babichenko et al. 2016]. Solving END-OF-A-LINE requires time
In Section 13.3 we will prove a quasi-polynomial lower bound on the running time for counting the number of communities in a social network. This result is also conditional, but requires the following much weaker #ETH assumption:
Hypothesis 2.3
#ETH [Dell et al. 2014]. Given a 3SAT formula, counting the number of satisfying assignments takes time 2Ω(n).
2.4 PCP Theorems
2.4.1 2CSP and the PCP Theorem
In the 2CSP problem (Constraint Satisfaction Problem), we are given a graph G = (V, E) on | V | = n vertices, where each of the edges (u, v) ∈ E is associated with some constraint function ψu, v : Σ × Σ → {0, 1} that specifies a set of legal “colorings” of u and v, from some finite alphabet Σ (2 in the term “2CSP” stands for the “arity” of each constraint, which always involves two variables). Let us denote by ψ the entire 2CSP instance, and define by OPT(ψ) the optimum (maximum) fraction of satisfied constraints in the associated graph G, over all possible assignments (colorings) of V.
The starting point of some of our reductions is the following version of the Probabilistically Checkable Proof (PCP) theorem, which asserts that it is NP-hard to distinguish a 2CSP instance whose value is 1, and one whose value is 1 − η, where η is some small constant:
Theorem 2.1
PCP Theorem [Dinur 2007]. Given a 3SAT instance φ of size n, there is a polynomial time reduction that produces a 2CSP instance ψ, with size |ψ| = n · polylog n variables and constraints, and constant alphabet size such that
• (Completeness) If OPT(φ) = 1 then OPT(ψ) = 1.
• (Soundness) If OPT(φ) < 1 then OPT(ψ) < 1 − η, for some constant η = Ω(1).
• (Graph) The constraint graph is d-regular, for some constant d, and bipartite.
See, e.g., the full version of Braverman et al. [2017]or Aaronson et al. [2014] for derivations of this formulation of the PCP theorem.
Notice that since the size of the reduction is near linear, ETH implies that solving the above problem requires near exponential time.
Corollary 2.1
Let ψ be as in Theorem 2.1. Then assuming ETH, distinguishing between OPT(ψ) = 1 and OPT(ψ) < 1 − η requires time
Label Cover
Definition 2.7
LABEL COVER. LABEL COVER is a maximization problem, and a special case of 2CSP. The input is a bipartite graph G = (A, B, E), alphabets, ΣB, ΣB and a projection πe : ΣA → ΣB for every e ∈ E.
The output is a labeling φA : A → ΣA, φΒ : Β → ΣB. Given a labeling, we say that a constraint (or edge) (a, b) ∈ E is satisfied if π(a, b) (φA(a)) = φB(b). The value of a labeling is the fraction of e ∈ E that are satisfied by the labeling. The value of the instance is the maximum fraction of constraints satisfied by any assignment.
We often