CS 6515/4540 · Exam 3 study notes

1. Las Vegas. Every pivot sequence sorts correctly; only the number of comparisons is random (average O(n log n), worst n²).
2. Monte Carlo with one-sided error: a prime is always classified correctly, but a composite can pass (remainder 1) and be wrongly called prime.
3. Monte Carlo. It always returns a cut in n − 2 contractions, but contracting a min-cut edge early destroys that cut. Success probability ≥ 2/(n(n−1)).
4. Las Vegas (MU §6.2.1): the output is checked (count crossing edges in poly time), so it is always correct; the number of rounds is geometric with mean 1/p ≤ m/2 + 1.
5. Monte Carlo, and in fact only an expectation guarantee: E[#satisfied] ≥ m/2, but one run can be worse.

1. X ~ Bin(4, 1/4): Pr[X = 2] = C(4,2)(1/4)²(3/4)² = 27/128. Pr[X = 0] = (3/4)⁴ = 81/256. E[X] = np = 1 (linearity over 4 indicators, each with expectation 1/4).
2. Y ~ Geo(1/4): Pr[Y = 3] = (3/4)²(1/4) = 9/64. Pr[Y > 3] = all three first trials fail = (3/4)³ = 27/64. E[Y] = 1/p = 4 (MU Lemma 2.9 / memoryless argument).
3. Y, the geometric one: “repeat until success”. This is exactly why Pr[success within N runs] = Pr[Y ≤ N] = 1 − (1 − p)^N.

1. Pr[X = n + k | X > k] = (1−p)^n+k−1p / (1−p)^k = (1−p)ⁿ⁻¹p = Pr[X = n]. Past failures don't change the future.
2. Let Xᵢ be the boxes bought while holding exactly i − 1 types. A new type appears with probability pᵢ = (n − i + 1)/n, so Xᵢ ~ Geo(pᵢ) and E[Xᵢ] = n/(n − i + 1). Linearity: E[X] = Σ n/(n−i+1) = n·H(n) = n ln n + Θ(n). n = 5: 137/12 ≈ 11.42. n = 10: ≈ 29.29 (compare n ln n = 23.03).

Write X = X₁ + ⋯ + Xₙ where Xᵢ = 1 if toss i is heads, else 0. Each Xᵢ is Bernoulli, so E[Xᵢ] = 1·Pr[Xᵢ = 1] + 0 = 1/2. By linearity of expectation (no independence needed), E[X] = Σ E[Xᵢ] = n/2.

For Bin(n, p) the same decomposition gives E[Xᵢ] = p, so E[X] = np. Compare MU §2.2, where the direct computation from the pmf takes a page.

E[X] = 50, so (E[X])² = 2500. E[X²] = (1/99)Σi² = 9950/3 ≈ 3316.67 > 2500. In general E[X²] − (E[X])² = E[(X − E[X])²] ≥ 0. Jensen: for convex f, E[f(X)] ≥ f(E[X]). (f(x) = x² is convex.) The trap: E[X²] ≠ (E[X])², whereas linearity only covers sums and constant multiples.

Markov: P(X ≥ 24) ≤ E[X]/24 = 6/24 = 1/4.

For a = 4 the bound is 6/4 = 3/2 > 1, which says nothing (every probability is ≤ 1). Markov is only useful for thresholds well above the mean. It can never show that the variable is unlikely to be near or below its mean.

Let I be the indicator of the event {X ≥ a}. Then I ≤ X/a pointwise: if X ≥ a then I = 1 ≤ X/a; otherwise I = 0 ≤ X/a because X ≥ 0. Taking expectations (expectation preserves ≤), Pr[X ≥ a] = E[I] ≤ E[X/a] = E[X]/a. ∎

Where X ≥ 0 was used: the case I = 0. Without it, X/a could be negative and the pointwise inequality fails.

1. Markov: ≤ (n log n)/(10 n log n) = 1/10.
2. ≤ (2 n ln n)/(10 n ln n) = 1/5.
3. No. The worst case is still n². Markov only says the probability of a run 10× slower than average is at most 1/10. That's the trade-off the professor stressed: “you can say something meaningful but not exact.”

1. False. Linearity holds for any random variables, even dependent ones (Lec 16/17: “independence is not required”). The max-cut edge indicators are dependent, and linearity still applies.
2. False. It needs X ≥ 0. Counterexample: X = −1 or +1 with probability ½ each, a = 1: Pr[X ≥ 1] = ½, but E[X]/a = 0.
3. True. E[I] = 1·Pr[I=1] + 0·Pr[I=0]. This is the step behind every “E[Xₑ] = Pr[e crosses]”.
4. False. Lec 16 typed notes: “The guarantees are always taken over the algorithm's random choices, not over a presumed random input distribution.” The input is fixed and worst case.
5. True. Definition on the Lec 16 typed notes (Karger is the example).
6. True. MU Lemma 2.9: E[X] = Σᵢ Pr[X ≥ i] = Σᵢ (1−p)ⁱ⁻¹ = 1/p.

1. (m − |Δ|)/m = 6/8 = 3/4. The proof uses |Δ|/|E| ≤ 2/|V|, giving ≥ 1 − 2/6 = 2/3. The true value is larger, as it should be (the bound is worst case).
2. deg(1)=2, deg(2)=3, deg(3)=3, deg(4)=3, deg(5)=3, deg(6)=2, all ≥ 2 = |Δ|. (Each vertex alone is a cut, so its degree is at least the min-cut size.)
3. 2/(n(n−1)) = 2/30 = 1/15 ≈ 0.0667. The exact 6/35 ≈ 0.1714 is above it. Consistent.
4. This graph has 3 min cuts ({1}|rest, {6}|rest, {1,2,3}|{4,5,6}). Returning any of them counts as success, so the probability adds over the disjoint events. The theorem is about one fixed Δ.

Preservation. If the algorithm never contracts an edge of Δ, the final two supervertices are exactly the two sides of Δ, so it returns Δ. (Contracting an edge not in Δ keeps Δ a min cut of the contracted graph: every edge of Δ survives and contraction creates no smaller cut.)

Step probabilities. Let e₁, …, e_n−2 be the contracted edges. Before step k (given e₁, …, e_k−1 ∉ Δ) the graph has n − k + 1 vertices, all of Δ, and E_k edges, so Pr[e_k ∉ Δ | past good] = 1 − |Δ|/E_k.

Degree bound. In the current graph each vertex v alone is a cut of size deg(v), so deg(v) ≥ |Δ|. Summing, 2E_k = Σ deg(v) ≥ |Δ|(n − k + 1), i.e. |Δ|/E_k ≤ 2/(n − k + 1).

Chain rule and telescoping. Pr[success] = ∏_k=1ⁿ⁻² Pr[e_k ∉ Δ | past good] ≥ ∏ (1 − 2/(n−k+1)) = ∏ (n−k−1)/(n−k+1) = (n−2)/n · (n−3)/(n−1) · (n−4)/(n−2) ⋯ 2/4 · 1/3 = 2·1/(n(n−1)). ∎

(1) The output must be a real cut of G. The edges between the final two supervertices are exactly the original edges crossing that partition. Merging parallel copies would undercount the cut's size, and we'd compare wrong sizes across runs.

(2) The probability analysis counts them. “Uniformly at random” is over current edges with multiplicity, and the degree bound 2|E| = Σ deg(v) ≥ |Δ|·|V| needs deg(v) to count every surviving original edge. With parallel copies merged, a min-cut edge could be chosen with higher probability than the bound allows.

1. C(5,2) = 10 min cuts. Full enumeration gives each probability exactly 1/10 = 2/(5·4) = 1/10, so the theorem is tight here. The 10 probabilities sum to 1.
2. For distinct min cuts Δ₁, …, Δ_t, the events “the run returns Δᵢ” are disjoint, and each has probability ≥ 2/(n(n−1)). Their total is ≤ 1, so t ≤ n(n−1)/2.

1. p = 2/90 = 1/45.
2. 1 − (1 − p)^N: N = 45 gives ≥ 0.6362 (about 1 − 1/e, since N = 1/p); N = 100 gives ≥ 0.8943.
3. Need e^−pN ≤ 0.01, i.e. N ≥ ln(100)/p = 45·ln 100, so N = 208 suffices. (The smallest N with (1 − p)^N ≤ 0.01 is 205; either answer is fine if justified.) By hand: ln 100 ≈ 4.6, and 45 × 4.6 ≈ 207.

1. (1 − p)^N ≤ e^−pN = e^{−(2/(n(n−1)))·α n(n−1) ln n} = e^{−2α ln n} = n^−2α. For α = 1 that is 1.000×10^-6: success ≥ 1 − one in a million.
2. Same computation with half as many runs: pN = α ln n, so the failure bound is n^−α. The constant in N just moves into the exponent.
3. About n(n−1) ln n = 6,900,848 runs (board version, α = 1), each O(n²)-ish. That's O(n² log n) runs: polynomial.

Failure after N trials ≤ (1 − 1/n²)^N ≤ e^−N/n². We need e^−N/n² ≤ n⁻³ ⇔ N/n² ≥ 3 ln n ⇔ N ≥ 3n² ln n. So O(n² log n) repetitions. (E.g. n = 10: 691 runs; n = 100: 138,156.) This matches the typed notes' general rule O(p⁻¹ log(1/δ)) with p = n⁻², δ = n⁻³.

We can't recognize success: given a cut, we can't check that it's minimum without already knowing the min-cut size, which is the thing we're computing. Instead, run N independent times and keep the smallest cut found. If any run produces a min cut, the kept one is a min cut, so Pr[success] ≥ 1 − (1 − p)^N. What makes it work: the size of a cut is easy to compute, so we can compare candidates by objective value even though we can't certify optimality (Lec 17 typed notes: “We need not know which trial succeeded if we can select the best candidate by its objective value”).

1. False. Monte Carlo: it may return a non-minimum cut. Its running time is fixed (n − 2 contractions).
2. True. p⁻¹ = n⁵ is polynomial; N = n⁵·c·ln n runs give failure ≤ n^−c (the boosting principle).
3. False. You'd need about 2ⁿ runs to make (1 − 2⁻ⁿ)^N small. That isn't polynomial.
4. False. Failure probability ≤ 1/n², not 0: it's “with high probability”, not “always”.
5. True. The bound 1 − 2/(n−k+1) shrinks as fewer vertices remain. The professor: “at the end you need to get really lucky.”
6. True. The lecture's slow method: run max-flow for every pair (s, t) and keep the smallest min s–t cut, since the global min cut separates some pair.

Suppose Pr[X ≥ μ] = 0. Then every value with positive probability is < μ, so μ = E[X] = Σ_x<μ x·Pr[X = x] < Σ_x<μ μ·Pr[X = x] = μ, a contradiction. (The strict inequality holds because the probabilities sum to 1, so some term has positive probability.) The case Pr[X ≤ μ] = 0 is symmetric: all mass is > μ, giving μ > μ. ∎

Use: “some outcome achieves at least the average”, so an object with value ≥ μ exists.

1. Edge uv: condition on u's side; v independently lands on the other side with probability ½. (Equivalently, 2 of the 4 equally likely outcomes split u and v.)
2. Let Xₑ be the indicator of e crossing, so |C(A,B)| = Σₑ Xₑ. By linearity (the Xₑ are not independent, and that doesn't matter), E = Σₑ Pr[Xₑ = 1] = m/2.
3. By the probabilistic method (5.1), Pr[|C| ≥ m/2] > 0, so such a cut exists. Since OPT ≤ m, a random cut has expected size m/2 ≥ OPT/2.

In a triangle, if two edges cross then the third cannot: two vertices are on one side and the third on the other, so exactly 0 or 2 edges cross. So Pr[all three cross] = 0 ≠ (½)³. The exact distribution is Pr[X=0] = 1/4, Pr[X=2] = 3/4, with E[X] = 3/2 = 3·½, as linearity predicts. Linearity adds expectations of any random variables; independence would be needed only for products.

Random assignment: a clause with kⱼ ≥ k distinct literals fails only if all its literals are false, with probability 2^−kⱼ ≤ 2^−k. By linearity, E[#satisfied] ≥ m(1 − 2^−k), and by the expectation argument some assignment achieves at least that. For m = 40, k = 3: ≥ 35 clauses.

1. Split E[X] at m/2: m/2 = Σ_i<m/2 i Pr[X=i] + Σ_i≥m/2 i Pr[X=i] ≤ (m/2 − 1)(1 − p) + m·p, since the small values are ≤ m/2 − 1 and the large ones ≤ m. Rearranging: m/2 ≤ m/2 − 1 + p(m/2 + 1), so p ≥ 1/(m/2 + 1).
2. For odd m the largest integer below m/2 is (m−1)/2, giving m/2 ≤ (m−1)/2·(1 − p) + mp ⇒ p ≥ (1/2)/((m+1)/2) = 1/(m + 1). m = 8: p ≥ 1/5. m = 9: p ≥ 1/10. Both are inverse-polynomial, which is all that boosting needs.
3. Repeat: sample a random cut, count crossing edges, stop when ≥ m/2. The output is always correct, so it's Las Vegas. The number of samples is geometric with mean 1/p ≤ m/2 + 1 (m = 8: ≤ 5; m = 9: ≤ 10). Alternatively, run a fixed number N of samples and keep the best (Monte Carlo, failure ≤ (1 − p)^N).

Final cut size 7 ≥ m/2 = 9/2 (here it is even optimal: brute force gives max cut 7). Shortcut: E[cut | ·] = (crossing edges among placed vertices) + ½·(all other edges), so you only compare the new vertex's placed neighbors: put it opposite the majority.

Charge each edge to its later endpoint in the processing order, so every edge is charged exactly once. When vertex v is placed, let d_v be the number of its already-placed neighbors. Putting v on the side opposite the majority of them makes at least ⌈d_v/2⌉ ≥ d_v/2 of these edges cross, and later placements never change whether these edges cross. Summing over v: crossing edges ≥ Σ d_v/2 = m/2, because Σ_v d_v = m. ∎

Start: E = Σ (1 − 2^−kⱼ) = 29/8.

Final assignment satisfies 5 of 5 clauses (≥ 29/8; brute-force optimum 5). Each conditional expectation is computed clause by clause: a satisfied clause counts 1, a falsified one 0, and a clause with f free literals and no true literal counts 1 − 2^−f.

1. False. Existence only. Finding needs an extra step: the probability bound plus boosting (Las Vegas), or derandomization.
2. False. Deterministic for a fixed order, but different orders can give different cuts, all with ≥ m/2 edges (Nov 3 recap).
3. False. Max-Cut is NP-hard (MU §6.2.1; the professor: “finding the largest cut can take us a long time”). Min-cut is in P.
4. True. By symmetry: swapping A and B doesn't change the cut size.
5. True. The number of samples is geometric with mean 1/p ≤ m/2 + 1 (MU §6.2.1).
6. True. It finds ≥ m/2 ≥ OPT/2 edges, deterministically.

A fixed k-clique is monochromatic with probability 2·2^−C(k,2) (all edges red or all blue). There are C(n,k) cliques, so by the union bound Pr[some monochromatic K_k] ≤ C(n,k)·2^−C(k,2)+1. If this is < 1, the complement event has positive probability, so a good coloring exists. For n = 1000, k = 20: C(1000,20)·2⁻¹⁸⁹ = 4.327×10^-16 < 1. ✓

d = 2m/n = 6. E[surviving vertices] = n/d and E[surviving edges] = (nd/2)(1/d)² = n/(2d). Deleting one endpoint per edge leaves ≥ X − Y vertices, so E[IS size] ≥ n/d − n/(2d) = n/(2d) = n²/(4m). Here n²/(4m) = 25/3 ≈ 8.33. Since a set size is an integer, some independent set has ≥ 9 vertices.

The proof uses Pr[clause fails] = (½)³ for every clause. A unit clause fails with probability ½ and a 2-clause with ¼, so the expected fraction can drop to ½. E.g. the formula (x) ∧ (¬x): fair coins satisfy exactly 1 of 2 clauses. Only the general bound E ≥ m/2 survives. (Also needed: the three literals are distinct variables, so the events are independent.)

Constraint: z ≤ y₁ + (1 − y₂) + y₃.

Satisfying, e.g. x = (T, T, F): RHS = 1 + 0 + 0 = 1, so z can be 1 and the maximization sets it to 1. The clause is counted.

Unsatisfying, the unique one x = (F, T, F): RHS = 0 + 0 + 0 = 0, so z = 0. The clause is not counted.

1. max z₁ + z₂ + z₃ s.t. z₁ ≤ y₁ + (1 − y₂), z₂ ≤ y₂, z₃ ≤ (1 − y₁) + (1 − y₂), with y, z ∈ {0,1} (ILP), or 0 ≤ y, z ≤ 1 (LP).
2. OPT = 2: no assignment satisfies all three. LP* = 2.5.
3. Every integer solution is LP-feasible and the LP maximizes over a larger set (relaxation).
4. Fair coins: ¾ + ½ + ¾ = 2. LP rounding with ŷ = (½, ½): also 2.0000. Both are ≥ (1 − 1/e)·LP* and ≥ ½·OPT, as guaranteed.

1. Fails only if all three are false: 0.5·0.7·0.8 = 0.2800, so Pr = 0.7200.
2. 1 − (1 − 1/3)³ = 0.7037 = β₃·1 (here Σŷ = ẑ = 1, so the AM–GM bound equals β₃ẑ). (1 − 1/e)·1 = 0.6321. Order: 0.7200 ≥ 0.7037 ≥ 0.6321.
3. ẑ ≤ (1 − 0.9) + (1 − 0.6) = 0.5000. Literal probabilities: Pr[¬x₁ true] = 0.1, Pr[¬x₂ true] = 0.4. Pr[sat] = 1 − 0.9·0.6 = 0.4600 ≥ β₂ẑ = ¾·0.5 = 0.3750. ✓ (For negated literals, use 1 − ŷᵢ as the literal's probability.)

g(z) = 1 − e^−z is concave (e^−z is convex, and the negative of a convex function is concave). Any z ∈ [0,1] is the convex combination z = (1 − z)·0 + z·1, so concavity gives g(z) ≥ (1 − z)g(0) + z·g(1) = (1 − z)·0 + z(1 − 1/e) = (1 − 1/e)z. ∎ (The curve lies above its chord from (0, 0) to (1, 1 − 1/e).)

Let Cⱼ have k literals with satisfaction probabilities p₁, …, pₖ (pᵣ = ŷᵢ for xᵢ, 1 − ŷᵢ for ¬xᵢ). The LP constraint says Σpᵣ ≥ ẑⱼ. The variables are distinct and independent, so Pr[sat] = 1 − ∏(1 − pᵣ). AM–GM on the k numbers 1 − pᵣ: ∏(1 − pᵣ) ≤ ((1/k)Σ(1 − pᵣ))^k = (1 − Σpᵣ/k)^k ≤ (1 − ẑⱼ/k)^k. So Pr[sat] ≥ 1 − (1 − ẑⱼ/k)^k =: f(ẑⱼ). f is concave on [0,1] with f(0) = 0, so f(z) ≥ f(1)·z = βₖz. Finally (1 − 1/k)^k ≤ e⁻¹ (from 1 − x ≤ e^−x), so βₖ ≥ 1 − 1/e.

Linearity: E[#sat] = Σⱼ Pr[Cⱼ sat] ≥ (1 − 1/e)Σⱼẑⱼ = (1 − 1/e)LP* ≥ (1 − 1/e)OPT. ∎

1. The LP is a relaxation, so its value can exceed the best integer value (5.66667 > 5).
2. Fair: 37/8 ≥ m/2 = 3.5. LP rounding: 4.8148 ≥ (1 − 1/e)·LP* = 3.5820 ≥ (1 − 1/e)·OPT.
3. E[max] ≥ average = 4.7199 ≥ ¾·LP* = 4.2500.

Take the clause (x₁ ∨ ⋯ ∨ xₖ), k ≥ 3, with ŷᵢ = 1/k for all i. Then Σŷᵢ = 1, so ẑ = 1 is feasible. Every ŷᵢ < ½, so threshold rounding sets all of them false and the clause fails. Randomized rounding fails only with probability (1 − 1/k)^k ≤ 1/e. The coins exploit the fractional mass spread across the literals; the threshold throws it away.

The better factor is always ≥ ¾ and the sum is always ≥ 3/2 (minimum 1.5000, at k = 1 and k = 2). Fair coins win for k ≥ 3, the LP wins for k = 1, and they tie at k = 2.

max(M₁, M₂) ≥ (M₁ + M₂)/2 pointwise, so E[max] ≥ ½(E[M₁] + E[M₂]). For a clause Cⱼ of size k: Pr_fair[Cⱼ sat] = αₖ ≥ αₖẑⱼ (since ẑⱼ ≤ 1) and Pr_LP[Cⱼ sat] ≥ βₖẑⱼ. Summing over clauses with linearity: ½(E[M₁] + E[M₂]) ≥ Σⱼ ½(αₖ + βₖ)ẑⱼ ≥ ¾ Σⱼ ẑⱼ = ¾·LP* ≥ ¾·OPT. ∎

Why not the video's version: “for each clause take whichever algorithm is better” describes a different, imaginary per-clause choice. The algorithm picks one whole assignment, so you must average.

1. False. The guarantee is in expectation; a single run can be lower (Lec 18 typed notes).
2. False. It's at least: the relaxation has more feasible points (LP* ≥ OPT).
3. False. Only the yᵢ are rounded. The resulting assignment determines which clauses are satisfied.
4. True. Håstad: doing better than 7/8 is NP-hard, and 0.88 > 0.875.
5. False. 7/8 needs exactly 3 distinct literals per clause; unit clauses are satisfied with probability only ½.
6. True. LP4: “Linear programming is solvable in polynomial time… integer linear programming is NP-hard”, shown via Max-SAT → ILP.

1. 8 ≤ OPT ≤ 19. Min problem: the LP relaxation gives OPT ≥ 7.4, and OPT is an integer, so OPT ≥ 8. The cover found is feasible, so OPT ≤ 19.
2. 27 ≤ OPT ≤ 30. Exactly-3 clauses: E[fair coins] = 7·30/8 = 26.25, so some assignment satisfies ≥ 27 (integer). The run's 24 is a weaker lower bound. Upper: OPT ≤ m = 30. The expected guarantee says nothing about this single run, so “24 ≥ (1 − 1/e)OPT” is not valid.
3. 7 ≤ OPT ≤ 14. Upper: the returned cover. Lower: 14 ≤ 2·OPT. The independent set gives only OPT ≤ 20 − 5 = 15 (its complement is a cover, §11.3), which is weaker than 14.

f outputs at most O(n²) symbols (it can't write more than its running time), so B's algorithm runs on N = O(n²): O((n²)³) = O(n⁶), plus O(n²) for f. Polynomial. Polynomials are closed under composition and sums, which is the professor's “sequence and nest efficient steps and stay efficient” idea. That's what makes “solve A via B” efficient whenever B is.

• Search problem: given an input I and a candidate solution S, a verifier checks in polynomial time whether S is a solution for I.
• NP: the class of all search problems. P: the search problems that can be solved in polynomial time (P ⊆ NP).
• NP-hard: every problem in NP reduces to it (f and g poly time). NP-complete: NP ∩ NP-hard.

No. NP-hard problems “don't have to be search problems”. Max-SAT or ILP as optimization problems are NP-hard but not in NP under this definition, because you can't verify optimality in poly time.

1. In NP (checking a path's length against a shortest-path computation is poly) and in P.
2. In NP: count the vertices and check no edge inside. Poly-time solvability is unknown; it's NP-complete.
3. Not known to be in NP (the lecture: “not a search problem” as seen in class): verifying optimality would need the DP, which is pseudo-polynomial (time depends on B, exponential in its bit length). Also not known to be in P. Knapsack-search (value ≥ g) is in NP (problem 9.10).
4. Not in NP as an optimization problem (you can't check that the count is maximum), but NP-hard (SAT → Max-SAT).
5. In NP and in P (SCCs of the implication graph).

1. Given S, check Σ_i∈Swᵢ ≤ B and Σ_i∈Svᵢ ≥ g: two sums of at most n numbers, O(n log W) bit operations, polynomial in the input size. It has the search form (a solution or NO), so it's in NP.
2. Binary search on g ∈ [0, V]: if the box finds a subset for goal g, the optimum is ≥ g; if it says NO, the optimum is < g. That takes ⌈log₂(V + 1)⌉ calls. The box's answer at the largest feasible g is an optimal subset. V is written in O(n log V_max) bits, so log V is at most the input size, and the total time is polynomial.
3. “≤ g” would be trivial: the empty set always has value 0 ≤ g. We want to push the value up.
4. V = 20: binary search makes 5 calls (≤ ⌈log₂ 21⌉ = 5), and the optimum is 13, using items {2, 4} (weights 4 + 5 = 9, values 5 + 8 = 13).
5. Not known to be in NP: we know no polynomial-time way to verify that a subset is optimal, since our only optimum-finder is the O(nB) DP, which is pseudo-polynomial. Not known to be in P either. (Proving it's not in NP would prove P ≠ NP.)

Correct: 1, 2, 5, 6

1. ✔ Verify T is a spanning tree (BFS/DFS) and compare its weight with Kruskal's/Prim's MST: O(m log n).
2. ✔ Kruskal/Prim find it in polynomial time.
3. ✘ Not known: verifying optimality needs the pseudo-polynomial DP.
4. ✘ Nondeterministic polynomial time. P ⊆ NP.
5. ✔ Each clause has at most 2n literals, so O(n) per clause, m clauses (NP1 video).
6. ✔ If one NP-complete problem were in P, every NP problem would be (all reduce to it), so P = NP. Contrapositive.
7. ✘ Wrong direction: that only shows B is no harder than SAT. Reduce a known NP-complete problem TO B.

Two requirements fail. (1) The ⇔ fails: f(I) always has a solution, even when I has none. (2) No useful g: the answer (the edge 1–2) carries no information about I, so no poly-time g can turn it into a solution of I. f and g must be designed together so that a solution of f(I) can be translated back.

(b) A → B. Then a poly-time algorithm for B would solve A, and hence everything in NP. B → A would only say B is no harder than A.

Shortest path → SAT holds (shortest path ∈ NP, Cook–Levin). SAT → shortest path is not known: it would put SAT in P and give P = NP. Reductions are not symmetric.

1. B is NP-hard.
2. A ∈ P (solve A by f, then B's algorithm, then g).
3. Nothing about B. Easy problems reduce to hard ones all the time.
4. Nothing about A. Everything in NP reduces to an NP-hard B, easy problems included.
5. B is NP-hard (from A) and in NP, so B is NP-complete.

B ∈ P ⇒ A ∈ P (reductions carry easiness backward). A is NP-hard, so every NP problem reduces to A and is in P. P = NP. (So we don't expect such a reduction to exist, but that's what it would imply.)

1. False. No restriction beyond: I solvable ⇔ f(I) solvable, g recovers a solution, f and g poly time (Nov 10 Q&A).
2. False. Unknown. We don't know how to; doing so would prove P = NP (Nov 10 Q&A: “We don't know yet”).
3. True. A problem we can solve in poly time can be verified by solving it (KT 8.10).
4. False. NP-hard problems “don't have to be search problems” (e.g. optimization Max-SAT, ILP).
5. False. “They very much depend on A and B.”
6. True. Everything in NP reduces to it (KT 8.12; Nov 10 lecture).
7. True. Compose: f_BC∘f_AB and g_AB∘g_BC are poly time (KT 8.9). Polynomials compose to polynomials.

1. Binary search on k ∈ [0, n] (KT §8.1).
2. Let α be the max size. For each vertex v in turn: if G − v still has an independent set of size α, delete v permanently (some optimum avoids it); otherwise keep it. At the end every remaining vertex is needed, so the remaining graph is an independent set of size α. That's n more calls. (Derived argument; the lecture left this as an exercise.)

Reduce SAT → Max-SAT (SAT is NP-hard by Cook–Levin).

f: given a CNF formula φ with m clauses, pass the same φ to Max-SAT. Identity: poly time.

⇔ and g: run Max-SAT to get an assignment a maximizing the number of satisfied clauses. Output a if it satisfies all m clauses, otherwise “no”. If φ is satisfiable, the maximum is m, so a satisfies everything and we return a satisfying assignment. If φ isn't satisfiable, no assignment satisfies all m, so a doesn't and we correctly say “no”. Checking the count is linear time. So a poly-time Max-SAT algorithm would solve SAT, and Max-SAT is NP-hard.

(Max-SAT is not in NP as an optimization problem, so it is NP-hard, not NP-complete.)

f: variables yᵢ (one per Boolean variable) and zⱼ (one per clause), all in {0,1}; maximize Σzⱼ subject to zⱼ ≤ Σ_i∈Cⱼ⁺ yᵢ + Σ_i∈Cⱼ⁻(1 − yᵢ). Size O(n + m) variables and m constraints: poly.

Correctness: for 0/1 y, the RHS is 0 exactly when every literal of Cⱼ is false, which forces zⱼ = 0. Otherwise zⱼ can be 1, and maximization sets it. So the ILP optimum equals the max number of satisfiable clauses, achieved at y = the assignment. g: read xᵢ = T iff yᵢ = 1. Chain: SAT → Max-SAT → ILP, so ILP is NP-hard.

1. (x1∨x2): ¬x1→x2, ¬x2→x1. (x1∨¬x3): ¬x1→¬x3, x3→x1. (¬x2∨¬x4): x2→¬x4, x4→¬x2. (¬x3∨x4): x3→x4, ¬x4→¬x3.
2. No cycles, so all 8 SCCs are single vertices. No x shares an SCC with ¬x, so f is satisfiable.
3. Assigning in reverse topological order (x = T iff x's SCC comes after ¬x's) gives x1 = T, x2 = T, x3 = F, x4 = F. Check: (T∨T), (T∨T), (F∨T), (T∨F). All true.

Edges: ¬x1→x2, ¬x2→x1, ¬x1→¬x2, x2→x1, x1→x2, ¬x2→¬x1, x1→¬x2, x2→¬x1. Then x1 → x2 → ¬x1 and ¬x1 → x2 → x1, so x1 and ¬x1 are in the same SCC. In fact all four literals form 1 SCC. Same SCC ⇒ same truth value, but x1 and ¬x1 can't be equal. Unsatisfiable.

(a) The clause is false only when a = b = F. Exactly then ¬a → b fails (T → F) and ¬b → a fails. In all other cases both implications hold.

(b) Each edge u → v is an implication that a satisfying assignment must respect: if u is true then v is true. If u and v are in the same SCC, there are paths u ⇝ v and v ⇝ u, so u true ⇒ v true and v true ⇒ u true. Equal values.

(c) x and ¬x always have opposite values, so they can't be in one SCC of a satisfiable formula. (The converse, that otherwise it's satisfiable via the topological-order assignment, is the video's lemma.)

1. Unit (¬x₁): set x₁ = F. Delete clauses containing ¬x₁ (the unit clause itself) and delete the false literal x₁ from (x₁ ∨ x₄): f′ = (x₃ ∨ ¬x₂) ∧ (x₄) ∧ (¬x₄ ∨ x₂) ∧ (¬x₃ ∨ x₄). Unit (x₄): set x₄ = T, delete (x₄) and (¬x₃ ∨ x₄), shrink (¬x₄ ∨ x₂) to (x₂): (x₃ ∨ ¬x₂) ∧ (x₂). Unit (x₂): set x₂ = T, giving (x₃). Unit (x₃): set x₃ = T, giving the empty formula.
2. Yes: x₁ = F, x₂ = T, x₃ = T, x₄ = T (the only satisfying assignment).
3. The unit clause (a) can only be satisfied by making a true, so every satisfying assignment does that. Clauses containing a are then already satisfied (safe to delete), and the literal ¬a is false (safe to delete from its clauses). Nothing else changes.
4. An empty clause can't be satisfied, so output NO. (This case is my addition; the video only shows the satisfiable path.) Otherwise, after elimination every clause has exactly 2 literals and the SCC algorithm takes over.

1. Write the path as α = γ₀ → γ₁ → ⋯ → γ_ℓ = β. Each edge γᵢ → γᵢ₊₁ comes from the clause (¬γᵢ ∨ γᵢ₊₁), which also contributes the edge ¬γᵢ₊₁ → ¬γᵢ. Following these edges backwards gives ¬β = ¬γ_ℓ → ⋯ → ¬γ₀ = ¬α.
2. For α, β ∈ S there are paths both ways, so by (a) there are paths ¬β ⇝ ¬α and ¬α ⇝ ¬β: all of S̄ lies in one SCC. Applying the same argument to that SCC shows it can't contain anything outside S̄, so S̄ is exactly an SCC. If an edge u → ¬α entered S̄ from outside (u ∉ S̄, α ∈ S), then by (a) the edge α → ¬u would exist, with ¬u ∉ S: an edge leaving S. A sink has none, so S̄ has no incoming edges: it is a source.
3. A clause with a literal in S is satisfied, because that literal is true. A clause (ℓ ∨ b) with ℓ ∈ S̄ gives the edge ¬ℓ → b with ¬ℓ ∈ S. S is a sink, so b ∈ S, and b is true. S ≠ S̄ because no x shares an SCC with ¬x, so no literal gets both values. Removing S ∪ S̄ (closed under negation) leaves exactly the implication graph of the remaining clauses, with the same SCCs, so we can repeat. Total time O(n + m).

(a) C′ = (x1 ∨ x2 ∨ y1) ∧ (¬y1 ∨ x3 ∨ y2) ∧ (¬y2 ∨ x4 ∨ y3) ∧ (¬y3 ∨ x5 ∨ y4) ∧ (¬y4 ∨ x6 ∨ x7).

(b) ⇒: let xᵢ be a true literal. Its clause is satisfied. Set y₁, …, y_j = T for every y appearing before xᵢ's clause and the rest F. Each clause to the left contains some yₜ = T, and each clause to the right contains some ¬yₜ with yₜ = F. ⇐ (contrapositive): if all xᵢ are false, clause 1 forces y₁ = T, then clause 2 forces y₂ = T, …, then the last clause (¬y_k−3 ∨ x_k−1 ∨ xₖ) is false. So C′ is unsatisfiable.

(c) k − 2 = 8 clauses and k − 3 = 7 new variables. Each clause of length k becomes O(k) clauses, so the total size is linear in the formula. g: restrict the 3-SAT assignment to the original variables.

Each middle clause needs three slots: the connector ¬y_t−1 from the previous clause, one original literal, and the connector yₜ to the next. With two slots you can't both chain the clauses and carry an original literal, so the equivalence breaks. That's consistent with 2-SAT ∈ P (unless P = NP, no such reduction exists).

In NP: the candidate solution is an assignment; the verifier evaluates each clause in linear time. NP-hard: SAT → 3-SAT by clause splitting (10.6). Clauses with ≤ 3 literals are copied unchanged, longer ones are split, and the original variables' values are kept.

Reduce 3-SAT → k-SAT with f = identity: every 3-SAT formula already has ≤ 3 ≤ k literals per clause, so it is a k-SAT input with exactly the same satisfying assignments (g = identity). Polynomial trivially. (Reducing to a more general problem is often this easy. Compare VC → Set Cover.)

In NP. Given an assignment, check each clause in O(1) time: O(m).

Reduce 3-SAT → Exact-4-SAT. Let φ be a 3-SAT formula (every clause has 1 to 3 literals; remove repeated literals, and drop clauses containing both x and ¬x since they're always true).

f: for each clause C with j < 4 literals, create 4 − j fresh variables z and replace C by the 2^4−j clauses “C ∨ (one sign pattern of the z's)”. For example, a 3-literal clause (a ∨ b ∨ c) becomes (a ∨ b ∨ c ∨ z) ∧ (a ∨ b ∨ c ∨ ¬z). Clause counts per original clause: 1 → 8, 2 → 4, 3 → 2 (literals → clauses). So there are ≤ 8m clauses and ≤ 3m new variables: polynomial (linear).

(⇒) If an assignment satisfies φ, keep it and set the z's arbitrarily. Every new clause contains an original clause C, which is true.

(⇐) Take an assignment satisfying f(φ) and suppose some original C is false under it. Among C's padded copies, pick the one whose z-literals are all false under this assignment (choose each sign opposite to that z's value). That copy has every literal false: contradiction. So every C is true, and the assignment restricted to the original variables satisfies φ.

g: drop the z's. Linear. Together with “in NP”, Exact-4-SAT is NP-complete.

Shape lesson (§12.2): “same problem, extra size condition” ⇒ reduce from the original and pad.

In NP: check that the assignment satisfies φ (O(nm)) and count the true variables (O(n)).

SAT → Stingy SAT: f(φ) = (φ, n) where n is the number of variables. ⇔: every assignment has ≤ n true variables, so φ has a satisfying assignment ⇔ (φ, n) has a stingy one. g = identity. f and g are linear.

Shape lesson (§12.2): a generalization of a known hard problem (extra parameter k) ⇒ set the parameter so it becomes the special case.

1. Vertices (one per literal occurrence): x@C1, ¬x@C2, y@C2, ¬y@C3, z@C3, x@C3, so 6 vertices. Clause edges: ¬x@C2–y@C2; ¬y@C3–z@C3, ¬y@C3–x@C3, z@C3–x@C3. Complement edges: x@C1–¬x@C2, ¬x@C2–x@C3, y@C2–¬y@C3. Total 7 edges. k = m = 3.
2. S = {x@C1, y@C2, z@C3} is independent and |S| = 3 ⇒ x = T, y = T, z = T. Check: (T), (F ∨ T), (F ∨ T ∨ T). All satisfied.
3. No: x@C1 and ¬x@C2 are joined by a complement edge (a contradiction: x and ¬x both “true”).

In NP. Given S, check |S| ≥ k and that no edge joins two vertices of S: O(|V| + |E|).

Reduce 3-SAT → IS. Transformation f. For a formula φ with m clauses (≤ 3 literals each), make one vertex per literal occurrence. Join all vertices of the same clause (clause cliques), and join every pair of complementary literals x, ¬x, in any clauses. Set k = m. Size: ≤ 3m vertices, ≤ 3m clause edges, ≤ (3m)² complement edges. Polynomial.

(⇒) If φ is satisfiable, pick one true literal per clause. The m picked vertices are in different clauses (no clique edge), and no two are complementary because both would have to be true (no complement edge). So we get an independent set of size m.

(⇐) If G has an independent set S of size m, it has exactly one vertex per clause (the cliques allow at most one) and never both x and ¬x. Set those literals true and the remaining variables arbitrarily. This is consistent and satisfies every clause.

Recovery g. Given S, read off the assignment as above in linear time. If IS reports no set of size m, φ is unsatisfiable by (⇒).

(a) Fine: the clause is satisfied more than once, but the independent set takes exactly one vertex per clause, because the clause clique allows at most one. (b) Prevented by the complement edge y–¬y: such an S isn't independent. (c) The cliques cap |S| at one per clause, so m is the maximum possible, and reaching m forces one true literal in every clause.

(a) For u, v ∈ S: uv ∉ E ⇔ uv ∈ Ê. “No pair in S is an edge of G” is the same as “every pair in S is an edge of Ĝ”.

(b) In NP: check all pairs of K are edges (O(k²)). NP-hard: IS → Clique with f(G, k) = (Ĝ, k), which takes O(n²) to complement. By (a), G has an independent set of size k ⇔ Ĝ has a clique of size k, and g returns the same set.

(c) Yes: complementing twice gives back G, so Clique → IS is the same map. (Both are NP-complete, so reductions exist both ways.)

(a) ⇒: for any edge uv, u and v are not both in S, so one of them is in V∖S. ⇐: if u, v ∈ S were adjacent, neither endpoint would be in V∖S, contradicting the cover.

(b) IS → VC: (G, k) ↦ (G, n − k). G has an independent set of size ≥ k ⇔ a vertex cover of size ≤ n − k; g = complement. VC → IS: (G, k) ↦ (G, n − k), symmetric.

(c) Yes, that's the ⇐ direction of (a).

No. Take a perfect matching on n vertices (n/2 disjoint edges). Min VC = n/2, so a 2-approximation may legally return all n vertices. Its complement is ∅, but the max IS is n/2. The ratio is 0: no constant factor survives. (In the star, the min VC is just the center, and the max IS is everything else.) Exact reductions preserve optimal solutions, not approximation ratios.

(a) Add s and t; s → u for all u ∈ V₁; direct each edge u → v (V₁ to V₂); v → t for all v ∈ V₂; all capacities 1. Poly time.

(b) Suppose two edges of M share u ∈ V₁. Then the flow out of u is ≥ 2, but the only edge into u is s → u, with capacity 1, so the flow in is ≤ 1. This contradicts conservation. The same argument at v ∈ V₂ (only one edge out, v → t) rules out sharing a V₂ endpoint. Conversely, each matching edge gives a unit path s → u → v → t, so max flow value = max matching size. (Uses that max-flow algorithms return integral flows when capacities are integers.)

(c) Matching → Max-Flow, and Max-Flow ∈ P, so bipartite matching ∈ P. Reductions to easy problems prove easiness.

f: U = E (the edges); for each vertex i, Sᵢ = the edges incident to i; same k. A vertex cover {i₁, …, i_ℓ} touches every edge ⇔ S_i₁ ∪ ⋯ ∪ S_iℓ = E. So covers of size ≤ k correspond exactly. Poly time; g maps the chosen sets back to their vertices. Since VC is NP-hard, Set Cover is NP-hard (and in NP: check the union).

1. False. Reductions in the other direction don't have to be inverses (Nov 12 Q&A). The 3-SAT → IS graphs are very special (small cliques plus links).
2. True. Complements: sizes add to n, so maximizing |S| minimizes |V∖S|.
3. False. Perfect-matching example: the 2-approximate cover can be all of V, leaving ∅.
4. True. That's the ⇐ direction.
5. False. It shows matching is in P (reduction TO an easy problem). Hardness would need a reduction FROM a hard problem.
6. True. Both via the complement graph Ĝ.

1. In NP: given M, check |M| ≤ k and that every edge has an endpoint in M: O(|V| + |E|).

2. Known hard problem: Independent Set (NP-hard via 3-SAT). Reduce IS → VC.

3. f: (G, k) ↦ (G, n − k). O(1) extra work beyond copying G.

4. ⇔: (⇒) if S is independent with |S| ≥ k, then V∖S covers every edge (an edge inside S would contradict independence), and |V∖S| ≤ n − k. (⇐) If M is a cover with |M| ≤ n − k, then V∖M is independent (an edge inside it would be uncovered), and |V∖M| ≥ k.

5. Poly + recovery: f and g (g(M) = V∖M) are linear time. If VC answers “none”, IS has none either, by (⇒).

Student 1 reduced 2-SAT → IS. That only says IS is at least as hard as 2-SAT, which tells us nothing about 2-SAT (wrong direction). Hardness needs a known hard problem → 2-SAT, which would imply P = NP since 2-SAT ∈ P.

Student 2 proved only (⇒). Without (⇐), a clique of size m in Ĝ might not come from any satisfying assignment, so the black box's answer can't be trusted for “no” instances. Both directions are required.

In NP: check size n′/2 and independence.

Reduce IS → HALF-IS. Input (G, k), n = |V|. Assume 2 ≤ k ≤ n (k = 1 is trivial).

f: If 2k ≤ n, add n − 2k isolated vertices: n′ = 2n − 2k, target n′/2 = n − k = k + (n − 2k). If 2k > n, add t = 2k − n universal vertices, adjacent to every vertex and to each other: n′ = 2k, target k. Linear/quadratic size.

⇔ (case 2k ≤ n): (⇒) an independent set of size k in G plus all n − 2k isolated vertices is independent, of size n − k. (⇐) An independent set of size n − k in G′ uses at most n − 2k new vertices, so it has ≥ k vertices of G, which are independent in G.

⇔ (case 2k > n): (⇒) an independent set of size k in G is still independent in G′ (no new edges among old vertices). (⇐) Any independent set containing a universal vertex has size 1 < k (k ≥ 2), so an independent set of size k in G′ lies entirely in G.

g: drop the added vertices. Poly time throughout.

f: U = E; for each vertex v, S_v = the set of edges incident to v; same k. Poly.

⇔: S_u ∩ S_v ≠ ∅ ⇔ the edge uv exists (an edge is in both incidence sets exactly when it joins u and v). So a family {S_v : v ∈ T} is pairwise disjoint ⇔ T is independent, and sizes match. g: T = the indices of the chosen sets. In NP: check pairwise disjointness. So Set Packing is NP-complete.

1. Independent Set (a packing problem with conflicts as edges): identity-like map.
2. Vertex Cover (covering edges with vertices).
3. Clique (or IS on Ĝ).
4. 3-SAT (identity, since 3 ≤ 4), or SAT with clause splitting.
5. SAT → “max” version with the same instance (Max-SAT style: satisfiable ⇔ the optimum satisfies all).

Full solution (what to write)

1. At most n(n−1)/2 min cuts. Let λ be the min-cut size and let Δ₁, …, Δ_t be all the distinct min cuts. Fact (lecture, §4.2): for any fixed min cut Δ, one run of the contraction algorithm outputs Δ with probability ≥ 2/(n(n−1)). (Reason: with j supervertices left and Δ intact, every supervertex has degree ≥ λ, so there are ≥ jλ/2 edges and Pr[contract an edge of Δ] ≤ λ/(jλ/2) = 2/j. Multiply ∏_j=3ⁿ(1 − 2/j) = 2/(n(n−1)).)

Let Aᵢ = “the run outputs Δᵢ”. A run outputs exactly one cut, so the events Aᵢ are disjoint. Therefore 1 ≥ Pr[A₁ ∪ ⋯ ∪ A_t] = Σᵢ Pr[Aᵢ] ≥ t · 2/(n(n−1)), so t ≤ n(n−1)/2 = O(n²). (Tight: the cycle Cₙ has exactly this many, problem 15.5.)

2. α-small cuts. First assume 2α is an integer and set r = 2α (so r ≥ 3, because α > 1). Fix a cut C = (S, T) with |C| ≤ αλ. Modified algorithm: contract uniformly random edges until r supervertices remain; then output a uniformly random partition of those r supervertices into two non-empty sides.

Contraction phase. Suppose j supervertices remain and no edge of C has been contracted yet. Each supervertex X is one side of a cut (X, V∖X) of the original G, so deg(X) ≥ λ, and the multigraph has ≥ jλ/2 edges. The next edge is in C with probability ≤ αλ/(jλ/2) = 2α/j. So Pr[C survives until r remain] ≥ ∏_j=r+1ⁿ(1 − r/j) = ∏_j=r+1ⁿ(j − r)/j = (n − r)!·r!/n! = 1/C(n, r).

Final phase. If C survived, each side of C is a union of supervertices, so C is one of the 2^r−1 − 1 two-sided partitions of the r supervertices. It is chosen with probability 1/(2^r−1 − 1) ≥ 2^−(r−1).

Counting. Pr[output = C] ≥ 1/(C(n, 2α)·2^2α−1) for every α-small C. The events “output = C” are disjoint over different C, so #α-small cuts ≤ C(n, 2α)·2^2α−1 ≤ n^2α·2^2α−1/(2α)! = O_α(n^2α).

If 2α is not an integer, stop at r = ⌈2α⌉. Using ln(1 − x) ≥ −x/(1 − x): 1 − 2α/j ≥ exp(−2α/(j − 2α)), and Σ_j=r+1ⁿ 1/(j − 2α) ≤ 1 + ln n (first term ≤ 1, the rest ≤ ∫ ds/(s − 2α)). So the survival probability is ≥ e^−2α·n^−2α, and the count is ≤ e^2α·2^r−1·n^2α = O_α(n^2α). (Both product bounds are checked numerically in calc.py.)

1. Let Δ₁, …, Δ_t be the distinct min cuts and Aᵢ the event “the run returns Δᵢ”. A run returns exactly one cut, so the Aᵢ are disjoint. So 1 ≥ Pr[A₁ ∪ ⋯ ∪ A_t] = Σ Pr[Aᵢ] ≥ t·2/(n(n−1)), giving t ≤ n(n−1)/2 = O(n²).
2. The cycle Cₙ: λ = 2, and removing any 2 of the n edges splits it into two arcs, a cut of size 2. That's C(n,2) = n(n−1)/2 min cuts. (Enumeration for C₅: 10 min cuts, each returned with probability exactly 1/10.)

1. Every cut of a cycle cuts an even number of edges, and any even-size edge set defines a cut (go around the cycle alternating sides). So the α-small cuts number C(n,2) + C(n,4). For n = 10: 45 + 210 = 255.
2. Bound: C(10,4)·2³ = 1,680 ≥ 255 ✓. Since C(n,4) = Θ(n⁴) = Θ(n^2α), the exponent 2α can't be improved in general. (For n = 20: 5035 cuts vs bound 38,760.)

1. Every supervertex alone is a cut of G, so it has degree ≥ λ. So there are ≥ tλ/2 edges and Pr[pick a Δ-edge] ≤ λ/(tλ/2) = 2/t.
2. Chain rule over t = n, n−1, …, r+1: ∏ (1 − 2/t) = ∏ (t−2)/t, which telescopes to (r−1)r/((n−1)n). For n = 10, r = 4: 2/15. (r = 2 recovers 2/(n(n−1)).)
3. Same argument with |C| ≤ αλ: Pr[pick a C-edge] ≤ αλ/(tλ/2) = k/t. ∏_t=k+1ⁿ (t−k)/t = k!(n−k)!/n! = 1/C(n,k).
4. If C survived, it is one of the 2^k−1 − 1 cuts of the remaining graph, and a uniform choice picks it with probability ≥ 2^−(k−1). So Pr[output C] ≥ 1/(C(n,k)·2^k−1). The events “output C” are disjoint for different C, so the number of α-small cuts is ≤ C(n,k)·2^k−1 ≤ n^2α·2^2α−1 = O_α(n^2α). (Non-integer 2α: stop at ⌈2α⌉ and bound ∏(1 − 2α/t) by c_α·n^−2α using ln(1 − x) ≥ −x − x²; the same conclusion holds.)

Full solution (what to write)

(a) Assume (as “exactly three literals” means) the three literals of each clause are on distinct variables. Let a random assignment set each variable T/F independently with probability ½. For clause Cⱼ let Yⱼ = 1 if Cⱼ is satisfied. Cⱼ is false only if all three literals are false, which has probability (½)³ = 1/8. So E[Yⱼ] = 7/8. The number of satisfied clauses is W = Σⱼ Yⱼ. By linearity of expectation (no independence between clauses needed), E[W] = 7m/8 = 87.5% of m.

(b) The random assignment is uniform over all 2ⁿ assignments, so E[W] = (1/2ⁿ)·Σₐ W(a) = 7m/8: the expectation is the plain average of W over all assignments. Suppose some a₀ has W(a₀) < 7m/8, and suppose for contradiction that no assignment has W(a) > 7m/8. Then every term is ≤ 7m/8 and one is strictly smaller, so Σₐ W(a) < 2ⁿ·7m/8, i.e. E[W] < 7m/8. Contradiction. Hence some a₁ has W(a₁) > 7m/8.

(c) Take the 8 clauses on x₁, x₂, x₃ with all 2³ sign patterns: (x₁∨x₂∨x₃), (x₁∨x₂∨¬x₃), …, (¬x₁∨¬x₂∨¬x₃). Fix any assignment a. A clause is false under a iff each of its literals is false, which fixes the sign of every literal (use xᵢ if aᵢ = F, ¬xᵢ if aᵢ = T). So exactly one of the 8 clauses is false, and every assignment satisfies exactly 7 of 8 = 87.5%. (Brute-force checked in calc.py.)

1. A clause fails only when all 4 literals are false: one of the 16 equally likely settings of its variables. E[Wⱼ] = 15/16, and by linearity E[W] = 15m/16.
2. E[W] is the average of W(a) over all 2ⁿ equally likely assignments a: (1/2ⁿ)Σₐ W(a) = 15m/16. If W(a₀) < 15m/16 and every W(a) ≤ 15m/16, the average would be strictly below 15m/16, a contradiction. So some W(a) > 15m/16. (Exactness matters: with exactly 4 distinct literals, E is exactly 15m/16.)
3. All 16 clauses on x₁…x₄ with every sign pattern. Each assignment falsifies exactly the one clause whose literals are all false under it, so it satisfies 15 of 16.
4. Some assignment achieves ≥ the mean 75/4, and counts are integers, so ≥ 19.

(a) (x₁∨x₂) ∧ (x₁∨¬x₂) ∧ (¬x₁∨x₂) ∧ (¬x₁∨¬x₂): every assignment satisfies 3 of 4 (see the §15.2 figure). It's also the unsatisfiable 2-SAT example from §10.3. (b) A random assignment averages 3m/4, so some assignment reaches at least that. (c) ≥ ⌈15/4⌉ = 4.

Full solution (what to write)

(a) ILP. Variable xᵢ ∈ {0, 1} for each element i = 1, …, n (xᵢ = 1 means i ∈ S).

minimize Σᵢ xᵢ subject to Σ_{i ∈ Sⱼ} xᵢ ≥ 1 for every j = 1, …, m, and xᵢ ∈ {0, 1}.

Equivalence: if S is a hitting set, its indicator vector satisfies every constraint (S contains some i ∈ Sⱼ) and has objective |S|. Conversely a feasible 0/1 vector gives S = {i : xᵢ = 1}, which meets every Sⱼ, with |S| equal to the objective. So the optima are equal. The LP relaxation replaces xᵢ ∈ {0, 1} by 0 ≤ xᵢ ≤ 1. It is a relaxation of a minimization, so LP* = Σᵢ x*ᵢ ≤ OPT.

(b) The xᵢ are rounded independently. S misses Sⱼ exactly when xᵢ = 0 for every i ∈ Sⱼ, so P(S ∩ Sⱼ = ∅) = ∏_i∈Sⱼ(1 − x*ᵢ) and P(S ∩ Sⱼ ≠ ∅) = 1 − ∏_i∈Sⱼ(1 − x*ᵢ).

(c) Let k = |Sⱼ| ≥ 1. AM–GM on the k non-negative numbers 1 − x*ᵢ: ∏_i∈Sⱼ(1 − x*ᵢ) ≤ ((1/k)Σ_i∈Sⱼ(1 − x*ᵢ))^k = (1 − (1/k)Σ_i∈Sⱼx*ᵢ)^k ≤ (1 − 1/k)^k ≤ e⁻¹. The middle step uses the LP constraint Σ_i∈Sⱼx*ᵢ ≥ 1; the last uses 1 − y ≤ e^−y. So P(S ∩ Sⱼ ≠ ∅) ≥ 1 − 1/e ≈ 0.632.

(d) Rounds use fresh coins, so they are independent. For a fixed j, P(Sⱼ missed by all of the first t rounds) = ∏ over rounds of P(that round misses Sⱼ) ≤ e^−t. Let X_t = number of sets not yet hit after t rounds. By linearity, E[X_t] = Σⱼ P(Sⱼ missed) ≤ m·e^−t, which is ≤ 1 for t = ⌈ln m⌉. Let T = number of rounds until every set is hit. Then P(T > t) = P(X_t ≥ 1) ≤ E[X_t] ≤ m e^−t (Markov). With t₀ = ⌈ln m⌉ (so m e^−t₀ ≤ 1): E[T] = Σ_t≥0 P(T > t) ≤ t₀ + Σ_s≥0 m e^−t₀−s ≤ ⌈ln m⌉ + 1/(1 − 1/e) ≈ ⌈ln m⌉ + 1.582 = O(ln m).

(e) The output is the union of the T samples, so its size is ≤ Σ_r=1^T|S^(r)|. One round has E|S^(r)| = Σᵢ x*ᵢ = LP*. Whether round r happens (T ≥ r) depends only on rounds 1, …, r − 1, so it is independent of S^(r). Hence E[cost] ≤ Σ_r≥1 E[|S^(r)|·1{T ≥ r}] = Σ_r≥1 LP*·P(T ≥ r) = LP*·E[T] ≤ (⌈ln m⌉ + 1.582)·OPT. The output is always a valid hitting set and its expected size is within a factor ln m + O(1) = O(ln m) of OPT: an O(ln m)-approximation (in expectation).

1. min Σⱼ yⱼ s.t. Σ_{j: e∈Sⱼ} yⱼ ≥ 1 for every e ∈ U, yⱼ ∈ {0,1} (ILP), or 0 ≤ yⱼ ≤ 1 (LP). Every cover is LP-feasible with the same value and the LP minimizes over a superset, so LP* ≤ OPT.
2. e is missed only if none of its k sets is picked: Pr = ∏ᵢ (1 − y*_jᵢ) (independence). AM–GM: ≤ (1 − (Σᵢ y*_jᵢ)/k)^k ≤ (1 − 1/k)^k ≤ 1/e, using the constraint Σ ≥ 1 and 1 − x ≤ e^−x.
3. Rounds are independent: Pr[e missed by all t] ≤ (1/e)^t. Union bound over n elements: ≤ n·e^−t. t = ⌈ln(4n)⌉ gives ≤ 1/4 (n = 100: t = 6; n = 1000: t = 9).
4. One round picks Sⱼ with probability y*ⱼ, so E[# sets in a round] = Σ y*ⱼ = LP* ≤ OPT. The union of t rounds has at most the sum of the round sizes, so by linearity E ≤ t·LP* ≤ t·OPT.
5. Markov: Pr[size > 4t·OPT] ≤ 1/4. Union bound with (c): Pr[not a cover, or too big] ≤ 1/2. Repeat to boost (§4.3).

1. T > t means some element is uncovered after t rounds: ≤ n e^−t by 15.10(c). Tail sum: E[T] = Σ_t≥0 Pr[T > t] ≤ Σ_{t<⌈ln n⌉} 1 + Σ_s≥0 n e^{−⌈ln n⌉−s} ≤ ⌈ln n⌉ + Σ_s≥0 e^−s = ⌈ln n⌉ + 1/(1 − 1/e). (1/(1 − 1/e) ≈ 1.582; n = 100 gives E[T] ≤ 6.58.)
2. Let Cᵣ be the number of sets picked in round r, so the total is Σᵣ Cᵣ·1{T ≥ r}. The event {T ≥ r} (“not done after r − 1 rounds”) depends only on rounds 1…r−1, so it is independent of Cᵣ, and E[Cᵣ·1{T ≥ r}] = LP*·Pr[T ≥ r]. Summing: E[total] = LP*·Σᵣ Pr[T ≥ r] = LP*·E[T] ≤ (ln n + O(1))·OPT. That is an O(log n)-approximation in expectation.

U = {1}, S₁ = ⋯ = Sₖ = {1}, y* = (1/k, …, 1/k): LP* = 1 = OPT. Element 1 is covered unless all k coins fail: Pr = 1 − (1 − 1/k)^k (k = 3: 19/27). Threshold rounding picks all k sets (each y* = 1/k ≥ 1/k), a cover of size k = k·OPT. That's Exam 2 Q4's tight example. The two methods trade a factor k (deterministic, frequency k) against O(log n) (randomized, any instance).

Full solution (what to write)

(a) In one round Brito sees: the commitments (perfectly hiding, so they reveal nothing), the edge {u, v} he chose himself, and the two opened colors (C′(u), C′(v)) = (π(c₁), π(c₂)), where c₁ = C(u) ≠ c₂ = C(v) because C is proper. For any ordered pair (d₁, d₂) of different colors there is exactly one permutation π with π(c₁) = d₁ and π(c₂) = d₂ (the third color must go to the remaining one). π is uniform over the 3! = 6 permutations, so the revealed pair is uniform over the 6 ordered pairs of distinct colors, each with probability 1/6. This distribution is the same for every proper coloring C and every edge. Brito could generate it himself (pick an edge, pick two distinct random colors) without talking to Raquel, so he learns nothing except that the endpoints differ, which is exactly what 3-colorability implies. A fresh π each round makes the rounds independent, so nothing builds up over N rounds.

(b) Fix a round. Because commitments are binding, they fix one assignment C′ : V → {1, 2, 3} before Brito picks the edge. G is not 3-colorable, so some edge e* is monochromatic under C′. Brito's edge is uniform over the m edges and independent of C′, so he picks e* (and rejects) with probability ≥ 1/m. Hence P(pass a round) ≤ 1 − 1/m, even conditioned on everything that happened in earlier rounds (Brito's coins are fresh). Multiplying over rounds: P(pass all N rounds) ≤ (1 − 1/m)^N ≤ e^−N/m.

(c) It suffices that e^−N/m ≤ ε ⇔ N/m ≥ ln(1/ε) ⇔ N ≥ m ln(1/ε), so N = ⌈m ln(1/ε)⌉ works. (The exact minimum is ⌈ln ε / ln(1 − 1/m)⌉, slightly smaller.) Example: m = 15, ε = 10⁻³ gives N = 104 (exact minimum 101). An honest prover passes with probability 1: one-sided error.

1. The endpoints have different colors c₁ ≠ c₂, and π is uniform over the 2 permutations, so (π(c₁), π(c₂)) is (1,2) or (2,1), each with probability ½, whatever the coloring. Brito learns nothing beyond “the endpoints differ”.
2. Any committed coloring of a non-bipartite graph has ≥ 1 monochromatic edge. Brito hits it with probability ≥ 1/m, so a round is passed with probability ≤ 1 − 1/m. Rounds are independent (fresh π, fresh commitment, fresh challenge), so all N pass with probability ≤ (1 − 1/m)^N ≤ e^−N/m.
3. e^−N/m ≤ ε ⇔ N ≥ m ln(1/ε). For m = 15, ε = 10⁻³: N = 104 (the exact minimum with (14/15)^N ≤ 10⁻³ is 101).
4. Monte Carlo (fixed N rounds, can wrongly accept) with one-sided error: an honest prover is always accepted, and only a cheater can slip through.

(a) Zero knowledge fails: across rounds Brito sees colors under one fixed relabeling, so revealed edges stitch together into Raquel's actual coloring (up to one renaming). (b) Soundness fails: a single color is never “wrong”, so a cheater is never caught. (c) Soundness fails: after seeing {u, v}, Raquel just reveals two different colors, so every round passes even when G is not 3-colorable.

Correct: 1, 2, 4

1. ✔ Two supervertices remain, which is a partition of V.
2. ✔ The theorem, for each fixed Δ.
3. ✘ Monte Carlo: it may return a non-minimum cut.
4. ✔ p ≥ 2/(n(n−1)) ≥ 1/n² gives failure ≤ (1 − 1/n²)^{n² ln n} ≤ e^{−ln n} = 1/n.

Correct: 1, 3

1. ✔ Linearity, each edge ½.
2. ✘ Counterexample: a triangle never has all 3 edges crossing.
3. ✔ Probabilistic method (MU Lemma 6.2).
4. ✘ Counterexample: a triangle (m/2 = 1.5 is not an integer); also a single edge (X ∈ {0, 1}).

Correct: 1, 4

1. ✔ Each nonempty clause has probability ≥ ½.
2. ✘ Counterexample: (x) ∧ (¬x), where the expectation is 1 of 2.
3. ✘ Only in expectation.
4. ✔ Averaging argument with αₖ + βₖ ≥ 3/2.

Correct: 1, 3

1. ✔ Hardness flows forward.
2. ✘ Counterexample: shortest path → SAT.
3. ✔ Easiness flows backward.
4. ✘ Counterexample: shortest path → SAT again.

Correct: 1, 3

1. ✔ Solve, then verify by solving.
2. ✘ NP-hard problems need not be search problems.
3. ✔ SCCs of the implication graph.
4. ✘ NP-hard, but not in NP as an optimization problem, so not NP-complete.

Correct: 3

1. ✘ Required.
2. ✘ Required.
3. ✔ Not required (Nov 10 Q&A).
4. ✘ Required in the search setting.

Correct: 1, 2, 4

1. ✔ Both directions.
2. ✔ Edges flipped.
3. ✘ Counterexample: a perfect matching; the cover may be all of V.
4. ✔ Complements: optimal sets correspond.

Correct: 1, 2

1. ✔ (1 − 1/m)^N ≤ e^−N/m.
2. ✔ e^−ln(1/ε) = ε.
3. ✘ One-sided: honest provers always pass.
4. ✘ The revealed colors would stitch together the coloring (15.14a).

(a) 2 and 3. (1 ✘: Monte Carlo. 4 ✘: the degree argument counts every edge with multiplicity, and the output must be a real cut.)

(b) 2: B ∈ P ⇒ A ∈ P, and A is NP-hard ⇒ everything in NP is in P.

(c) 1 and 4. (2 ✘: never needs independence. 3 ✘: needs X ≥ 0. Counterexample: X = ±1, a = 1 gives Pr = ½ > 0 = E[X]/a.)

(d) |V| = 7 (one per literal occurrence), clause edges 5 (a triangle for C1, one edge each for C2 and C3), complement edges 4 (a–¬a, ¬c–c, b–¬b, c–¬c), total 9, k = m = 3. An independent set of size 3: ¬c@C1, ¬a@C2, ¬b@C3 ⇒ a = b = c = F. Check: (F∨F∨T), (T∨F), (T∨T). ✓

(e) I = 1{X ≥ a} ≤ X/a pointwise (uses X ≥ 0). Take expectations: Pr[X ≥ a] = E[I] ≤ E[X]/a.

(f) 40 ≤ OPT ≤ 44. Lower: some assignment satisfies at least the mean 40 (probabilistic method). Upper: the LP relaxation of a maximization satisfies LP* ≥ OPT. (m = 48 and the ½-guarantee give only weaker bounds: OPT ≤ 48, OPT ≥ 24.)

(a) See 15.5(a): the events are disjoint and each has probability ≥ 2/(n(n−1)). (b) See 15.7(a)–(b): per step ≥ 1 − 2/t, telescoping to r(r−1)/(n(n−1)). (c) The cycles Cₙ (15.5b).

Full solution: problem 15.10 (a)–(e).

1. Given H: check |H| ≤ k and that each Sⱼ meets H, in O(Σ|Sⱼ|).
2. f(G = (V, E), k): universe [n] = V, one set S_e = {u, v} for each edge e = uv, same k. (⇒) A vertex cover M with |M| ≤ k contains an endpoint of every edge, i.e. M ∩ S_e ≠ ∅ for all e: a hitting set of size ≤ k. (⇐) A hitting set H with |H| ≤ k meets every {u, v}, i.e. touches every edge: a vertex cover of size ≤ k.
3. f writes one 2-element set per edge, O(n + m). g = identity (H itself is the cover). If HITTING-SET reports none, G has no cover of size ≤ k, by (⇒).
4. All sets have size b = 2, so we get a 2-approximation for vertex cover. No contradiction: this reduction maps solutions to solutions with the same cost (VC is literally the special case b = 2), so ratios carry over. The §11.4 failure was for IS ↔ VC, where costs transform as k ↦ n − k.

(a) 1, 2, 3. (4 ✘: about 2ⁿ repetitions would be needed.)

(b) 2: FROM the known problem TO the new one.

(c) 1, 3, 4. (2 ✘: LP* ≥ OPT for a maximization.)

(d) Edges (two per clause, ¬a → b and ¬b → a): x1→x3, x2→¬x3, x2→x1, x3→¬x2, ¬x1→x2, ¬x1→¬x2, ¬x2→x1, ¬x2→x3, ¬x3→¬x1, ¬x3→x2. SCCs: {x1, ¬x2, x3} and {¬x1, x2, ¬x3}. No variable shares an SCC with its negation ⇒ satisfiable. The assignment rule (x true iff SCC(x) is later in topological order) gives x1 = T, x2 = F, x3 = T. Check: (T∨F), (F∨T), (F∨T), (F∨T), (T∨T). ✓

(e) If Pr[X ≥ μ] = 0, all mass is on values < μ, so μ = Σ x Pr[X = x] < μ Σ Pr[X = x] = μ, a contradiction.

(f) 18 ≤ OPT ≤ 30. Lower: a cut of size 18 exists. Upper: no cut exceeds m. The algorithm's guarantee (≥ m/2 = 15) is weaker than the observed 18, and “18 ≥ OPT/2” would only give OPT ≤ 36, weaker than 30. (Same trap as Exam 2 Q1(f): extra information can be useless.)

Full solution: problem 15.8 (a)–(c).

(a), (b), (d): see 15.13. (c) N ≥ m ln(10⁶) = 553 (exact minimum 546).

1. Check that the chosen sets number ≤ k and that their union is U: polynomial.
2. f(G, k): U = E; for each vertex v, S_v = the set of edges incident to v; same k. (⇒) A cover M with |M| ≤ k touches every edge, so ∪_v∈M S_v = E. (⇐) If ∪_v∈T S_v = E with |T| ≤ k, every edge has an endpoint in T, so T is a vertex cover.
3. |U| = m, n sets, total size 2m: linear. g maps chosen sets to their vertices. A “none” answer is correct by (⇒).
4. No exact poly-time algorithm is known: one would give P = NP, since VC → SET-COVER and VC is NP-hard. So a polynomial-time algorithm with a provable O(log n) factor is the realistic goal: it always returns a valid cover whose expected size is within O(log n)·OPT, and it never needs to know OPT.