<nowiki> Solution for Q1. Posted by Heemany Shekhar, Nag Mani, Revanth Akella

</nowiki>

Posted by Dean Johnson, Sharan Duggirala, Saketh Saxena

Q3: a mod 42, a mod 2 = 0, a mod 3 = 2, a mod 7 = 5

m1 = 42 / 2 = 21 m2 = 42 / 3 = 14 m3 = 42 / 7 = 6

t1 = 21^-1 mod 2 = 1 t2 = 14^-1 mod 3 = 2 t3 = 6^-1 mod 7 = 6

c1 = 21 * 1 = 21 c2 = 14 * 2 = 28 c3 = 6 * 6 = 36

a = (021) + (228) + (5*36) = 56 + 180 = 26 mod 42 = 26

<nowiki>((Solution by Dean Johnson, Sharan Duggirala and Saketh Saxena))

</nowiki>

<nowiki> Solution for Q2.

Posted by Heemany Shekhar, Nag Mani, Revanth Akella

</nowiki>

Team: Pratik, Niket, kunal

APPROX-VERTEX-COVER (I wrote APPROX-SET-COVER on board, please igore that )

Kunal, Niket, Pratik <nowiki>

</nowiki>

Q8 ) <nowiki>

</nowiki>

Vincent, Nick, Ravali

Problem 9 :

Nick, Vincent, Ravali

Problem 10 :

Siddharth, Shantanu, Shashank

Ans.5) Define NP, NP-complete, and NP-hard. Argue the problem of determining where every assignment to a 3-SAT instance is satisfying is NP-hard.

NP: A Language L belongs to NP if there exists a two input polynomial-time algorithm A and a constant c such that

L = { x ∈ {0,1}* : ∃y, |y| = O(|x|^{c}) and A(x,y)=1 }

NP-Complete: A Language L is NP-Complete if

1. L ∈ NP, and
2. L' ≤ L in polynomial time, for every L' ∈ NP

NP-Hard : A language which satisfies (2) but not necessarily (1) is called NP-Hard. We can say that NP-Complete is a subset of NP-Hard.

We are trying to solve the second part of this question, if anyone feels they have a solution, do upload.

Siddharth, Shantanu, Shashank

Ans 6. p-time reduction from 3-SAT to CLIQUE Let F=C_1 ∧ C2... ∧ C_k be an instance of 3SAT. For each C_r=(l^r_1∨l^r_2∨l^r_3), we put a triple of vertices into our graph G, v^r_1,v^r_2,v^r_3. We put an edge between vertices v^r_i and v^s_j if they are in different triples and their corresponding literals are not negations of each other. Let (G,k) be the output instance of CLIQUE. Notice if there is a satisfying assignment to F then if we look at the corresponding vertices v^r_j of at least one satisfied literal/clause, it will be a CLIQUE of size k in G. As there are no edges between vertices coming from the same clause, any CLIQUE of size k has to have at least one vertex v^r_j for each 1≤r≤k. Choosing an assignment so that the corresponding literals for each v^r_j evaluate to true gives a satisfying assignment. So the reduction works.