Consider language L such that A B are two graphs and A has

Consider language L = {<A,B> such that A, B are two graphs and A has a k-clique but B does not, for some k}. Is L in NP? Why?

Solution

Answer:

L is NP because Clique of a graph is NP . Let us say if graph has m nodes then at its first stage it will take O(k)O(m) = O(km) time . Similarly for the second stage it will take O(k^2m^2) time.Thus runs in polynomial time.