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

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⋅n2nk, 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.

'''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>

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,kG has a vertex cover of size logk}. (b) s-t-CONNECTIVITY = {G,s,tNodes s,t are connected in graph G}. (c) 3-COLORABILITY = {GThere 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}

'''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|.

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>

'''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.

Joseph Lee

``

'''Problem 9:''' Give a 32/31-approximation algorithm for the MAX-5SAT and prove that it works.

``

'''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 m clauses.

``

<u>Proof</u>

Define indicator Y_i = I{\text{clause } i \text{ is satisfied}}. 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,

Pr{\text{clause } i \text{ is not satisfied}} = (\frac{1}{2})^5 = \frac{1}{32}

Pr{\text{clause } i \text{ is satisfied}} = 1 - \frac{1}{32} = \frac{31}{32}

E[Y_i] = \frac{31}{32}\cdot1 + \frac{1}{32}\cdot0 = \frac{31}{32}

Let Y = \sum_{i=1}^mY_i, then 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.

``

Therefore, because an optimal algorithm yields m correct clauses, the approximation ratio is \frac{OPT}{E[Y]} = \frac{m}{\frac{31m}{32}} = \frac{32}{31}.

Posted by Matthew Jones and Lei Zhang.

'''Problem 4 Solutions: '''

Answers for a and b:

Answer for c:

1. Prove Cook's Theorem by Zidong Jiang and Xuesong Luo

L: Language in NP

c_i: Computer Hardware Configuration at Step i

A: Algorithm A(x,y) where x is input, y is the boolean output for verifying language L in O(|X|^c) steps

M: 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 i in M, output of C at layer i+1 correspond to configuration c_i computed in M at layer i

(3) Output of C is the value from A(x,y) after O(|X|^c) 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