Eric Tjon, Scott Fang Problem 8: Prove there is no p-time TSP approximation algorithm. For this proof, assume P != NP and that HAM-CYCLE is NP complete. We can reduce instances of HAM-CYCLE to TSP d-approximation where d >= 1. If there is a p-time TSP approximation algorithm, then we can solve HAM-Cycle in p time. This would mean P=NP, a contradiction. Reduction: Let G be an instance of HAM cycle, and G' be a fully connected graph on the same vertices for TSP. Create edge weights in the G': 1 if the vertices are connected in G and d*|V|+1 otherwise. Use d-approximation algorithm to find the approximate best path. If solution <= d*|V|, then there is a HAM cycle otherwise, no HAM cycle exists

-- May 13 - Final Review

Posted by: Tracy Ho, Parnika De '''Problem #1:''' '''Lagrange's Theorem:''' If (S,⊕) is a finite group and (S′,⊕) is a subgroup, then |S′| is a divisor of |S|. '''Chinese Remainder Theorem:''' Let n=n1⋅n2⋯nk, where the ni are pairwise relatively prime. Consider the correspondence a ⇔ (a1,...,ak) where ai = a mod ni. Then this is a bijection and preserves addition and product.

-- May 13 - Final Review

---- '''Question 2:''' For each of the following equations, find all solutions or state no solutions exists: <math>(a) 9x≡3mod60. (b) 34x≡5mod38. (c) 34x≡5mod57</math> <br/> <br/> Solutions by Joseph, Pratik and Vishal <br/> <br/> '''Solution (a):''' Solving <math>9x≡3mod60</math> <br/> <br/> By Solution Existence Theorem, an equation of the form <math>ax ≡ b(mod n) </math> has d distinct solutions modulo n, where <math>d = gcd(a,n)</math>, if <math>d|b</math>, or it has no solutions. <br/> <br/> So, in the example <math>d = gcd(9, 60) = 3</math>. <br/> Note, 3 divides 3. Hence, it has 3 solutions. <br/> Solutions are given by, <br/> <math> d = a * x^' + n * y^'</math> <br/> This equation solves for <math> x^' = 7 and y^' = -1</math> <br/> <br/> <math>x_0</math> is given by <math>x_0 = x^'(\frac{b}{d}) mod n</math> <br/> Substituting values, <math>x_0 = 7</math> <br/> <br/> <math>x_0 = (7 * (\frac{3}{3})) mod 60 = 7 </math> <br/> <br/> <math>x_i = (x_0 + i( \frac{n}{d} )) mod n,</math> for <math>i = 0,1,... </math> <br/> <br/> Substituting, <math>i = 0, 1, 2</math> gives us the required 3 solutions. <br/> Which are <math>7, 27, 47</math> ---- '''Solution (b):''' Solving <math>34x≡5mod38</math> <br/> <br/> So, in the example <math>d = gcd(34, 38) = 2</math>. <br/> But, 2 does not divide 5. Hence, it has no solutions. ---- '''Solution (c):''' Solving <math>34x≡5mod57</math> <br/> <br/> So, in the example <math>d = gcd(34, 57) = 1</math>. <br/> Note, 1 divides 5. Hence, it has exactly 1 solution. <br/> Solutions are given by, <br/> <math> d = a * x^' + n * y^'</math> <br/> This equation solves for <math> x^' = -5 and y^' = 3</math> <br/> <br/> <math>x_0</math> is given by <math>x_0 = x^'(\frac{b}{d}) mod n</math> <br/> Substituting values, <math>x_0 = -25</math> <br/> <br/> <math>x_0 = (-5 * (\frac{5}{1})) mod 57 = 32 </math> <br/> <br/> So 32 is the only solution which is also <math>x = -25 mod 57</math>

-- May 13 - Final Review

Problems #6 and 10: Team : Yaoyan Xi, Jonathan Mao, For each of the following problems, determine with proof or solid argument if it is in P, NPC, or likely NP - (NPC ∪ P): (a) log-VERTEX-COVER = {⟨G,k⟩∣∣G has a vertex cover of size logk}. (b) s-t-CONNECTIVITY = {⟨G,s,t⟩∣∣Nodes s,t are connected in graph G}. (c) 3-COLORABILITY = {⟨G⟩∣∣There is an assignment of the colors red, green, blue to vertices such that vertices connected by an edge always have different colors}. Answer: a) treat logk = k' , this is essentially Vertex-Cover (G, k) algorithm. Hence, this is NP problem, but it is neither P nor NPC because the loop has logk nested loops. <br> b) picking s and t from |V| takes n*(n-1) = n^2 - n , this problem can be done within polynomial time, hence this is P problem. <br> c) three color problem is a classic NP-complete problem. Reduce 3-SAT to 3-COLORABILITY. Find full proof online.<br> For Problem # 10: assume L = {50,51,55,70,71,82,83,84,99} and δ = 0.1, therefore calculate y and y/(1+ δ) as follows: and L' = {50, 70, 82, 99} {| |- | y || z || y/(1+δ) |- | 50 ||50 ||45.45454545 |- | 51 || ||46.36363636 |- | 55 || || 50 |- | 70 ||70|| 63.63636364 |- | 71 || ||64.54545455 |- | 82|| 82 ||74.54545455 |- | 83 || || 75.45454545 |- | 84 || || 76.36363636 |- | 99 ||99|| 90 |}

-- May 13 - Final Review

 APPROX-VERTEX-COVER(G)
 1 C = ∅
 2 E'= E[G]
 3 while E' ≠ ∅
 4    let {u, v} be an arbitrary edge of E'
 5    C = C ∪ {u, v}
 6    Remove from E' every edge incident with either u or v
 7 return C.

'''Problem 7''' Elly Fan, Yulan Jin, Lolitha Tupadha APPROX-VERTEX-COVER(G) 1 C = ∅ 2 E'= E[G] 3 while E' ≠ ∅ 4 let {u, v} be an arbitrary edge of E' 5 C = C ∪ {u, v} 6 Remove from E' every edge incident with either u or v 7 return C. To see that the cover returned is at most twice the optimal, let A denote the set of edges which were picked in line 4. In order to cover the edges in A, any vertex cover (including the optimal C*) must include at least one endpoint of each edge in A. No two edges in A share an endpoint, so no two edges from A are covered by the same vertex from C⋆. So |C*| ≥ |A|. On the other hand |C| = 2|A|.

-- May 13 - Final Review

Posted by: Tracy Ho, Parnika De '''Problem #10:''' '''TRIM(L,δ)''' L = (y[1], ..., y[m] L' = y[1] last = y[1] for i = 2 to m if y[i] > last * (1 + δ) append y[i] to L' last = y[i] return L' '''Example:'' L = <70, 71, 82, 84, 98, 109, 150, 200> δ = 0.1 y/(1+δ) <= z < = y '''Trimmed list'': L' = <70, 84, 98, 109, 150, 200>

-- May 13 - Final Review

'''Problem 3''' - Dylan Wang and Tim Chow Let p be the smallest prime bigger than the day of the month you were born on. Let q be the first prime which is more than twice this. Let e be the smallest odd number bigger than 1 relatively prime to φ(p⋅q). If these were used in RSA, what would be the public key, what would be the private key? Encode and decode the message 11. ((resource:final3.PNG|Resource Description for final3.PNG))

-- May 13 - Final Review

Joseph Lee @BT@@BT@ '''Problem 9:''' Give a 32/31-approximation algorithm for the MAX-5SAT and prove that it works. @BT@@BT@ '''Solution:''' Algorithm: randomly and independently set each variable to 0 or 1 with probability 0.5. For 5-SAT, this is a 32/31-algorithm for @BT@m@BT@ clauses. @BT@@BT@ <u>Proof</u> Define indicator @BT@Y_i = I{\text{clause } i \text{ is satisfied}}@BT@. Since no literal appears more than once in the same clause, and assuming that all variables do not appear in the same clause with its negation, assignment is independent. A clause is not satisfied if all of its literals are set to 0. Therefore, @BT@Pr{\text{clause } i \text{ is not satisfied}} = (\frac{1}{2})^5 = \frac{1}{32}@BT@ @BT@Pr{\text{clause } i \text{ is satisfied}} = 1 - \frac{1}{32} = \frac{31}{32}@BT@ @BT@E[Y_i] = \frac{31}{32}\cdot1 + \frac{1}{32}\cdot0 = \frac{31}{32}@BT@ Let @BT@Y = \sum_{i=1}^mY_i@BT@, then @BT@E[Y] = E[\sum_{i=1}^mY_i] = \sum_{i=1}^mE[Y_i] = \sum_{i=1}^m\frac{31}{32} = \frac{31}{32}m@BT@. @BT@@BT@ Therefore, because an optimal algorithm yields @BT@m@BT@ correct clauses, the approximation ratio is @BT@\frac{OPT}{E[Y]} = \frac{m}{\frac{31m}{32}} = \frac{32}{31}@BT@.

-- May 13 - Final Review

Posted by Matthew Jones and Lei Zhang. '''Problem 4 Solutions: ''' Answers for a and b: ((resource:Screen Shot 2019-05-13 at 2.39.17 PM.png|Resource Description for Screen Shot 2019-05-13 at 2.39.17 PM.png)) Answer for c: ((resource:Screen Shot 2019-05-13 at 2.39.26 PM.png|Resource Description for Screen Shot 2019-05-13 at 2.39.26 PM.png))

-- May 13 - Final Review

5. Prove Cook's Theorem by Zidong Jiang and Xuesong Luo @BT@L@BT@: Language in NP @BT@c_i@BT@: Computer Hardware Configuration at Step i @BT@A@BT@: Algorithm A(x,y) where x is input, y is the boolean output for verifying language@BT@ L@BT@ in @BT@O(|X|^c)@BT@ steps @BT@M@BT@: Circuit consists of AND, OR, NOT gates with C(y) as output, with following properies. (1) Output of C at main layer 1 of M maps to code c_0 at the start of algorithm A(x,y), which x is hard-coded input. (2) For each layer @BT@i@BT@ in M, output of C at layer @BT@i+1@BT@ correspond to configuration @BT@c_i@BT@ computed in M at layer @BT@i@BT@ (3) Output of C is the value from A(x,y) after @BT@O(|X|^c)@BT@ steps Since there are polynomial many layers in M, separated by polynomia size circuits Whole circuit is polynoimial size If boolean variable for y makes M true Then A(x,y) holds and x will be in L