26 Appendix C. Background on Asymptotic Notation, Algorithms and Complexity

C.1 Asymptotic Notation

\(\)f,g\( be monotone real-valued functions of \)N\(. We say \)f(N)\( is \)O(g(N))\( if there exist constants \)c, N_0 ≥0\(, independent of \)N\(, such that for every large enough \)N ≥N_0\(, \[ f(N) \leq c \cdot g(N). \] Equivalently, \)f(N)\( is \)O(g(N))\( if and only if \)_N ∞ f(N)/g(N) ≤C\( for some absolute constant \)C\(. \)

\(\)f,g\( be monotone real-valued functions of \)N\(. We say \)f(N)\( is \)Ω(g(N))\( if there exist constants \)ε, N_0 ≥0\(, independent of \)N\(, such that for every large enough \)N ≥N_0\(, \[ f(N) \geq \varepsilon \cdot g(N). \] Equivalently, \)f(N)\( is \)Ω(g(N))\( if and only if \)_N ∞ f(N)/g(N) ≥C\( for some absolute constant \)C\(. \)

\(\)f(N)\( is \)Θ(g(N))\( if and only if \)f(N)\( is \)O(g(N))\( and \)f(N)\( is \)Ω(g(N))\(. Equivalently, \)f(N)\( is \)Θ(g(N))\( if and only if \)_N ∞ f(N)/g(N) = C\( for some absolute constant \)C\(. \)

\(\)f(N)\( is \)o(g(N))\( if \)f(N)\( is \)O(g(N))\( but \)f(N)\( is not \)Ω(g(N))\(. Equivalently, \)f(N)\( is \)o(g(N))\( if and only if \)_N ∞ f(N)/g(N) = 0\(. \)

\(\)f(N)\( is \)ω(g(N))\( if \)f(N)\( is \)Ω(g(N))\( but \)f(N)\( is not \)O(g(N))\(. Equivalently, \)f(N)\( is \)ω(g(N))\( if and only if \)_N ∞ f(N)/g(N) = ∞\(. \)

C.1.1 Some Properties

\(\)α{O, Ω, Θ, o, ω}\(. If \)f(N)\( is \)α(g(N))\( and \)g(N)\( is \)α(h(N))\(, then \)f(N)\( is \)α(h(N))\(. \)

Case \(\)α= O\(.\) Since \(\)f(N)\( is \)O(g(N))\(, there are \)c_1, N_1\( so that \)f(N) ≤c_1 g(N)\( for all \)N ≥N_1\(. Since \)g(N)\( is \)O(h(N))\(, there are \)c_2, N_2\( so that \)g(N) ≤c_2 h(N)\( for all \)N ≥N_2\(. For every \)N ≥(N_1, N_2)\(, \)f(N) ≤c_1 g(N) ≤c_1 c_2 h(N)\(, so \)f(N)\( is \)O(h(N))\( with constants \)c_1 c_2\( and \)(N_1, N_2)\(. \)Case \(\)α= Ω\(.\) Symmetric to the above with the inequalities reversed: if \(\)f(N) ≥ε_1 g(N)\( for \)N ≥N_1\( and \)g(N) ≥ε_2 h(N)\( for \)N ≥N_2\(, then for \)N ≥(N_1,N_2)\(, \)f(N) ≥ε_1 ε_2 h(N)\(. \)Case \(\)α= Θ\(.\) Immediate from the \(\)O\( and \)Ω\( cases, since \)Θ\( means both \)O\( and \)Ω\( hold. \)Case \(\)α= o\(.\) Since \(\)f(N)\( is \)o(g(N))\( and \)g(N)\( is \)o(h(N))\(, using the limit characterization, \)_N∞ f(N)/g(N) = 0\( and \)_N∞ g(N)/h(N) = 0\(. Hence \[ \lim _{N\to \infty } \frac{f(N)}{h(N)} = \lim _{N\to \infty } \frac{f(N)}{g(N)} \cdot \frac{g(N)}{h(N)} = 0 \cdot 0 = 0, \] so \)f(N)\( is \)o(h(N))\(. \)Case \(\)α= ω\(.\) Using the limit characterization, \(\)_N∞ f(N)/g(N) = ∞\( and \)_N∞ g(N)/h(N) = ∞\(, so their product diverges to \)∞\(, giving \)_N∞ f(N)/h(N) = ∞\(, i.e. \)f(N)\( is \)ω(h(N))\(. \)

\(\)α{O, Ω, Θ, o, ω}\(. If \)f(N)\( is \)α(h(N))\( and \)g(N)\( is \)α(h(N))\(, then \)f(N) + g(N)\( is \)α(h(N))\(. \)

Case \(\)α= O\(.\) There are \(\)c_1, N_1\( with \)f(N) ≤c_1 h(N)\( for \)N ≥N_1\( and \)c_2, N_2\( with \)g(N) ≤c_2 h(N)\( for \)N ≥N_2\(. Then for \)N ≥(N_1, N_2)\(, \)f(N) + g(N) ≤(c_1 + c_2) h(N)\(, so \)f(N) + g(N)\( is \)O(h(N))\(. \)Case \(\)α= Ω\(.\) There are \(\)ε_1, N_1\( with \)f(N) ≥ε_1 h(N)\( for \)N ≥N_1\(, and similarly \)ε_2, N_2\( for \)g\(. Since \)h\( is (WLOG, being an asymptotic growth measure of interest here) eventually non-negative, for \)N ≥(N_1,N_2)\(, \)f(N) + g(N) ≥(ε_1 + ε_2) h(N)\(, so \)f(N)+g(N)\( is \)Ω(h(N))\(. \)Case \(\)α= Θ\(.\) Immediate from the \(\)O\( and \)Ω\( cases. \)Case \(\)α= o\(.\) Using the limit characterization, \(\)_N∞ f(N)/h(N) = 0\( and \)_N∞ g(N)/h(N) = 0\(, hence \)_N∞ (f(N)+g(N))/h(N) = 0 + 0 = 0\(, so \)f(N)+g(N)\( is \)o(h(N))\(. \)Case \(\)α= ω\(.\) Both \(\)_N∞ f(N)/h(N) = ∞\( and \)_N∞ g(N)/h(N) = ∞\(; since \)g(N)/h(N)\( is eventually non-negative, \)(f(N)+g(N))/h(N) ≥f(N)/h(N) ∞\(, so \)f(N) + g(N)\( is \)ω(h(N))\(. \)

\(\)α{O, Ω, Θ, o, ω}\(. If \)f(N)\( is \)α(h_1(N))\( and \)g(N)\( is \)α(h_2(N))\(, then \)f(N) ·g(N)\( is \)α(h_1(N) ·h_2(N))\(. \)

Case \(\)α= O\(.\) There are \(\)c_1, N_1\( with \)f(N) ≤c_1 h_1(N)\( for \)N ≥N_1\(, and \)c_2, N_2\( with \)g(N) ≤c_2 h_2(N)\( for \)N ≥N_2\(. Assuming (as is standard for the quantities under consideration) \)f,g,h_1,h_2\( are eventually non-negative, for \)N ≥(N_1,N_2)\(, \)f(N)g(N) ≤c_1 c_2 h_1(N) h_2(N)\(, so \)f(N)g(N)\( is \)O(h_1(N)h_2(N))\(. \)Case \(\)α= Ω\(.\) Symmetric, using \(\)f(N) ≥ε_1 h_1(N)\( and \)g(N) ≥ε_2 h_2(N)\( to get \)f(N) g(N) ≥ε_1 ε_2 h_1(N) h_2(N)\(. \)Case \(\)α= Θ\(.\) Immediate from the \(\)O\( and \)Ω\( cases. \)Case \(\)α= o\(.\) Using the limit characterization, \(\)_N∞ f(N)/h_1(N) = 0\( and \)_N∞ g(N)/h_2(N) = 0\(, so \[ \lim _{N \to \infty } \frac{f(N) g(N)}{h_1(N) h_2(N)} = \left(\lim _{N\to \infty } \frac{f(N)}{h_1(N)}\right) \cdot \left(\lim _{N\to \infty } \frac{g(N)}{h_2(N)}\right) = 0, \] so \)f(N)g(N)\( is \)o(h_1(N)h_2(N))\(. \)Case \(\)α= ω\(.\) Both \(\)_N∞ f(N)/h_1(N) = ∞\( and \)_N∞ g(N)/h_2(N) = ∞\(, so their product diverges to \)∞\(, giving \)f(N)g(N)\( is \)ω(h_1(N)h_2(N))\(. \)

C.2 Bounding Algorithm run time

\(\)A\( be an algorithm, and let \)t_A(x)\( be the number of steps taken by \)A\( on input \)x\(. The worst-case run time \)T(N)\( of \)A\( on inputs of size \)N\( is defined by \[ T(N) = \max _{x : x \text{ is of size } N} t_A(x). \] \)

\(\)n\( items, memory consists of registers with \)O(n)\( bits, with dedicated registers for the input (one per input item) and for the output. An (atomic) step of the algorithm is any basic operation on a constant number of such registers implementable in \)O(n)\( bit operations: loading or storing \)O(n)\( bits in a register, initializing a register, bitwise operations between registers (e.g. XOR), adding numbers stored in two registers, incrementing a register, and comparing the values of two registers. Operations such as multiplying or exponentiating numbers that fit in one register each are not considered single-step operations. \)

\(\)a_1, …, a_n; v\(. \\ \textbf{Output:} \)i\( such that \)a_i = v\( (any such \)i\(, if multiple exist), or \)-1\( if no such \)i\( exists. \begin{enumerate} \item For every \end{enumerate}\)1 ≤i ≤n\( do: \item [\hphantom {x}] \quad If \)a_i = v\( then return \)i\(. \item Return \)-1\(. \)

\(\)T(n)\( denote the worst-case run time of Algorithm~ \ref{alg:appC-simple-search} on inputs of size \)n\(. Then \)T(n)\( is \)O(n)\(. \)

\(\)a_1,…,a_n; v\( be an arbitrary input. The for loop runs at most \)n\( iterations, and each iteration (the comparison \)a_i = v\( and a potential return) takes \)O(1)\( time. By Lemma~ \ref{lem:appC-asym-multiplicative}, the total time for the loop is \)T_12 ≤O(n ·1) = O(n)\(. The final return statement (Step 3) takes \)T_3 = O(1)\( time. By Lemma~ \ref{lem:appC-asym-additive} and the fact that \)O(1)\( is also \)O(n)\(, \[ t_{\text{Algorithm C.2.1}}(a_1,\dots ,a_n;v) = T_{12} + T_3 \leq O(n) + O(1) \leq O(n). \] Since \)a_1,…,a_n;v\( was an arbitrary input of size \)n\(, this shows \)T(n)\( is \)O(n)\(. \)

\(\)T(n)\( denote the worst-case run time of Algorithm~ \ref{alg:appC-simple-search} on inputs of size \)n\(. Then \)T(n)\( is \)Ω(n)\(. \)

\(\)n ≥1\(, consider the specific input \)a_i’ = n+1-i\( for \)1 ≤i ≤n\( and \)v’ = 1\(. Then the condition \)a_i’ = v’\( is satisfied only when \)i = n\(, so the for loop runs exactly \)n\( times. Each iteration performs at least one comparison, taking \)Ω(1)\( time. Since \)n\( is \)Ω(n)\(, Lemma~ \ref{lem:appC-asym-multiplicative} gives \)T_12 ≥Ω(n ·1) = Ω(n)\( for this input, hence \[ t_{\text{Algorithm C.2.1}}(a_1',\dots ,a_n';v') \geq T_{12} \geq \Omega (n). \] Since for every \)n ≥1\( we have exhibited one input of size \)n\( on which the run time is \)Ω(n)\(, we conclude \)T(n)\( is \)Ω(n)\(. \)

\(\)Θ(n)\(. \)

\(\)T(n)\( is \)O(n)\() and Lemma~ \ref{lem:appC-simple-search-lower} (which shows \)T(n)\( is \)Ω(n)\(), together with the definition of \)Θ\(. \)

C.3 Randomized Algorithms

\(\)T(N)\( on inputs of size \)N\( is the worst case, over both inputs of size \)N\( and choices of internal random bits, of the number of steps taken. A randomized algorithm is called correct if for every input, it returns the correct output with probability at least \)2/3\( (the probability being over the internal random bits of the algorithm). \)

\(\)x {0,1}^n\(, determine whether \)wt(x) ≤n/3\( or \)wt(x) ≥2n/3\(. For inputs \)x\( with \)wt(x) (n/3, 2n/3)\( the algorithm may behave arbitrarily. We refer to this as the \)GapHamming\( problem. \)

\(\)x {0,1}^n\(. \\ \textbf{Output:} \)0\( if \)wt(x) ≤n/3\( and \)1\( if \)wt(x) ≥2n/3\(, with probability at least \)1 - ε\(. \begin{enumerate} \item \end{enumerate}\)s ←98 ·(1/ε)\(; \)C ←0\(. \item For \)j [s]\( do: \item [\hphantom {x}] \quad Pick \)i\( uniformly and independently at random from \)[n]\(; \)C ←C + x_i\(. \item If \)C < s/2\( then return \)0\(. \item Return \)1\(. \)

\(\)1 - ε\( for every \)x\( with \)wt(x) (n/3, 2n/3)\(. \)

\(\)wt(x) ≤n/3\(; the case \)wt(x) ≥2n/3\( is entirely analogous (with the roles of the two outputs swapped). Fix such an \)x\(. We show that at Step 4, \[ \Pr \left[C \geq \frac{s}{3} + \frac{s}{7}\right] \leq \varepsilon , \tag {C.2} \] which suffices to show the algorithm outputs \)0\(, as desired. For \)j [s]\(, let \)Y_j\( be the random bit \)x_i\( picked in the \)j\(-th iteration, so that \)C = ∑_j=1^s Y_j\( is a sum of independent binary random variables. By the additive Chernoff bound, since \)[Y_j = 1] ≤1/3\( for every \)j\( (as \)wt(x) ≤n/3\(), we have \)E[C] ≤s/3\(, and \[ \Pr \left[C {\gt} \mathbb {E}[C] + \frac{s}{7}\right] \leq e^{-\frac{s}{72} \cdot 2} \leq \varepsilon , \] where the last inequality follows from the choice \)s = 98 ·(1/ε)\(. Combined with \)E[C] ≤s/3\(, this gives (C.2), as desired. \)

\(\)x {0,1}^n\( sampled from either \)D_1/3\( or \)D_2/3\(. \\ \textbf{Output:} \)0\( if \)x\( was sampled from \)D_1/3\( and \)1\( otherwise, with probability at least \)1 - ε\(. \begin{enumerate} \item \end{enumerate}\)s ←98 ·(1/ε)\(; \)C ←0\(. \item For \)j [s]\( do: \)C ←C + x_j\(. \item If \)C < s/2\( then return \)0\(. \item Return \)1\(. \)

Unlike Algorithm 588, this algorithm is deterministic; it may err on specific inputs \(\)x\(, but is correct with high probability over the choice of \)x\( from \)D_1/3\( or \)D_2/3\(. \)

\(\)x\( be a random sample from \)D_1/3\( (resp. \)D_2/3\(). Then with probability at least \)1 - ε\( over the choice of \)x\(, Algorithm~ \ref{alg:appC-gap-hamming-average} outputs \)0\( (resp. \)1\(). \)

\(\)x ∼D_1/3\(; the other case is analogous. Let \)Y_j := x_j\( for \)j [s]\(; since \)x ∼D_1/3\(, the \)Y_j\( are independent binary random variables with \)[Y_j = 1] = 1/3\(, and \)C = ∑_j=1^s Y_j\(, exactly as in the proof of Lemma~ \ref{lem:appC-gap-hamming-sampling-correct} (with the \)Y_j\('s there replaced by these identically-distributed independent random variables). The same additive Chernoff bound computation as in that proof gives \[ \Pr \left[C \geq \frac{s}{3} + \frac{s}{7}\right] \leq \varepsilon , \] which implies Algorithm~ \ref{alg:appC-gap-hamming-average} outputs \)0\( with probability at least \)1-ε\(, as desired. \)

C.4 Efficient Algorithms

\(\)O(kn 2^k)\( (and hence in time \)2^O(k)\(, and in time \)2^O(n)\( when \)k = O(n)\(). \)

\(\)x {0,1}^k\(, i.e. \)2^k\( many iterations. For each candidate \)x\(, computing the number \)t\( of the \)n\( equations that \)x\( satisfies requires evaluating each of the \)n\( linear equations on \)x\(: each equation involves at most \)k\( variables, so evaluating all \)n\( equations takes \)O(kn)\( time, and comparing \)t\( against \)s\( and returning takes \)O(1)\( additional time. By Lemma~ \ref{lem:appC-asym-multiplicative}, the total run time is \)O(2^k ·kn) = O(kn 2^k)\(. \)

\(\)Mx = b\( over \)F_2\(, where \)M\( is \)n ×k\(. Gaussian elimination reduces \)M\( to row-echelon form using \)O(n)\( row operations, each of which touches a row of length \)O(k)\(, giving \)O(nk)\( per elimination round and \)O(n)\( rounds, for a total of \)O(n^2 k)\( (equivalently \)O(kn^2)\() field operations; back-substitution to check consistency and produce a solution (if one exists) takes a further \)O(nk)\( time. Each field operation over \)F_2\( takes \)O(1)\( time, giving the stated bound. \)

\(\)O(k+n)\(, hence polynomial time, since there are \)|V| = k\( vertices and \)|E| = n\( edges each processed once in \)O(1)\( time. For the correctness claim: over \)F_2\(, \)x_i + x_j = 1\( (i.e. XOR) holds exactly when \)x_i ≠x_j\(. Writing \)S = {i V : x_i = 1}\(, we have \)x_i ≠x_j\( exactly when exactly one of \)i,j\( is in \)S\(, i.e. exactly when \)(i,j)\( is an edge crossing the cut \)S\(. Hence the number of equations satisfied by \)(x_1,…,x_k)\( equals the number of edges crossing the cut \)S\(, i.e. the cut size of \)S\(. Thus \)(x_1,…,x_k)\( satisfies at least \)s\( of the \)n\( equations if and only if \)S\( is a cut of size at least \)s\(, which is exactly the correctness condition for a reduction from \)MaxCut(k,n,s)\( to \)MaxLinearEq(k,n,s)\(. The converse map \)(x_1,…,x_k) ↦S\( is likewise computable in \)O(k)\( time. \)

C.5 More on intractability

\(\)x Σ^*\(, the set of all (finite, including empty) strings over an alphabet \)Σ\(. A problem is defined by a subset \)L ⊆Σ^*\(; if \)x L\( we say \)x\( is a \textsc{Yes} instance, and otherwise a \textsc{No} instance. (We also use \)L\( to denote the problem itself.) An algorithm \)A\( solves \)L\( if for every \)x Σ^*\(, \)A(x) = Yes\( when \)x L\( and \)A(x) = No\( when \)x L\(. \)

\(\)Y, N ⊂Σ^*\(, where every \)x Y\( is a \textsc{Yes} instance and every \)x N\( is a \textsc{No} instance; we refer to the problem as \)(Y,N)\(. An algorithm \)A\( solves \)(Y,N)\( if for every \)x Y ∪N\(, \)A(x) = Yes\( when \)x Y\( and \)A(x) = No\( when \)x N\( (there is no constraint on the behavior of \)A\( on \)Σ^* ∖(Y ∪N)\(). Every decision problem \)L\( is a promise problem, taking \)Y = L\( and \)N = Σ^* ∖L\(. \)

\(\)P ⊆NP\( and \)promise-P ⊆promise-NP\(. \)

\(\)L P\(, solved by a polynomial time algorithm \)A_L\(. Define a verification algorithm \)R(x,y) := A_L(x)\( (ignoring \)y\(; take \)y\( to be, say, the empty string). Then \)R\( runs in polynomial time, and: if \)x L\(, then \)A_L(x) = Yes\(, so taking \)y\( to be the empty string, \)R(x,y) = Yes\(; if \)x L\(, then \)A_L(x) = No\(, so \)R(x,y) = No\( for every \)y\( (in particular the empty string, since \)R\( ignores \)y\( entirely). Hence the conditions of Definition~ \ref{def:appC-class-np} hold and \)L NP\(. The same argument, replacing \)A_L\( by a polynomial time algorithm solving \)(Y,N)\(, shows \)promise-P ⊆promise-NP\(. \)

\(\)L_1\( is polynomial time reducible to a decision problem \)L_2\(, denoted \)L_1 ≤_P L_2\(, if there is a polynomial time algorithm \)A\( such that for every potential input \)x\( for \)L_1\(, \)A(x)\( is a potential input for \)L_2\( with \)x L_1\( if and only if \)A(x) L_2\(. Similarly, a promise problem \)(Y_1,N_1)\( is polynomial time reducible to \)(Y_2,N_2)\( if there is a polynomial time algorithm \)A\( such that for every potential input \)x\( for \)(Y_1,N_1)\(, \)A(x)\( is a potential input for \)(Y_2,N_2)\( with \)x Y_1 A(x) Y_2\(, and \)x N_1 A(x) N_2\(. (Reductions where \)A\( is instead a randomized polynomial time algorithm and the if-and-only-if conditions hold with probability at least \)2/3\( are also considered.) \)

\(\)A\( be the polynomial time reduction witnessing \)L_1 ≤_P L_2\(, and let \)A_2\( be a polynomial time algorithm solving \)L_2\(. Define an algorithm for \)L_1\(: on input \)x\(, compute \)A(x)\( (polynomial time in \)|x|\(, hence \)|A(x)|\( is also polynomial in \)|x|\(), then run \)A_2\( on \)A(x)\( (polynomial time in \)|A(x)|\(, hence polynomial in \)|x|\( since \)|A(x)|\( is polynomial in \)|x|\(), and return the result. The composition of two polynomial time algorithms, where the output size of the first is polynomially bounded in the input size, is itself polynomial time. Correctness follows since \)x L_1 A(x) L_2 A_2(A(x)) = Yes\(. Hence \)L_1 P\(. \)

\(\)L\( is NP-complete if (1) \)L NP\(, and (2) every decision problem \)L’ NP\( is polynomial time reducible to \)L\(, i.e. \)L’ ≤_P L\(. A problem satisfying only (2) is called NP-hard. \)

\(\)L\( with \)L P\(, then \)P = NP\(. \)

\(\)P ⊆NP\(, so it suffices to show \)NP ⊆P\(. Let \)L’ NP\( be arbitrary. Since \)L\( is NP-complete, \)L’ ≤_P L\(. Since \)L P\( by assumption, Lemma~ \ref{lem:appC-reduction-transfers-p} gives \)L’ P\(. As \)L’\( was an arbitrary problem in \)NP\(, this shows \)NP ⊆P\(, hence \)P = NP\(. \)

\(\)L\( be an NP-complete problem. If \)L ≤_P L’\(, then \)L’\( is NP-hard. If, further, \)L’ NP\(, then \)L’\( is NP-complete. \)

\(\)L” NP\( satisfies \)L” ≤_P L’\(. Since \)L\( is NP-complete, every \)L” NP\( satisfies \)L” ≤_P L\( (Definition~ \ref{def:appC-np-complete}). Composing the polynomial time reduction from \)L”\( to \)L\( with the given polynomial time reduction from \)L\( to \)L’\( yields a polynomial time reduction from \)L”\( to \)L’\( (the composition of two polynomial time algorithms, where the intermediate output size is polynomially bounded, is polynomial time, and the two if-and-only-if membership conditions chain together): \)x L” A(x) L A’(A(x)) L’\(, where \)A, A’\( are the respective reduction algorithms. Hence \)L” ≤_P L’\( for every \)L” NP\(, so \)L’\( is NP-hard by definition. If in addition \)L’ NP\(, then \)L’\( satisfies both conditions of Definition~ \ref{def:appC-np-complete}, so \)L’\( is NP-complete. \)