# Need a polynomial time reduction from 3SAT to INDEPENDENT-SET

In order to show that a problem is NP hard one must provide a reduction from a known NP hard problem to this problem. My question is how to reduce 3SAT to INDEPENDENT-SET?

3SAT is a satisfiable 3 literals in a clause Boolean conjunctive normal formula. INDEPENDENT-SET is a set of vertices in a graph, no two of which are adjacent. I do know how to reduce 3SAT to a Clique, would that help?

• Try to reduce the maximum clique problem to the independent set problem. Hint: look at the what happens to a clique in the complement of the graph. – Discrete lizard Jan 8 '18 at 14:04
• Thank you, in order to turn a graph into it's complement(?), it would take more than a polynomial time. Assuming we agree a co-graph is where there is an edge there isn't one and vice versa. And I forgot to mention that I need the reduction to be in polynomial time. – Anwar Saiah Jan 9 '18 at 0:03
• "It would take more than polynomial time" I doubt that. Why do you think that? – Discrete lizard Jan 9 '18 at 7:29

If you can accomplish this, then for a boolean formula with $m$ clauses, there is an independent set of size $m$ in your constructed graph if and only if the boolean formula is satisfiable, thus giving the desired reduction.