Question

Show that clique decision problem is np hard in daa

Answer 1

The computational difficulty of theclique problem has led it to be used toprove several lower bounds in circuit complexity. The existence of a cliqueof a given size is a monotone graph property, meaning that, if a cliqueexists in a given graph, it will exist in any supergraph.


i hope help you

Answer 2

Answer:

The Clique Decision Problem belongs to NP-Hard – A problem L belongs to NP-Hard if every NP problem is reducible to L in polynomial time. ... Thus, if S is reducible to C in polynomial time, every NP problem can be reduced to C in polynomial time, thereby proving C to be NP-Hard.