Let us have a look how Reducilibility works.
- If B ∈ P and A ≤P B then A ∈ P
- If B ∈ NP and A ≤P B then A ∈ NP
- If B ∈ NP Complete and A ≤P B then A ∈ NP
- If B ∈ NP Complete and B ≤P A then A ∈ NP Hard
- If B ∈ NP complete and A ∈ NP and B ≤P A then A ∈ NP Complete
- If B∈ undecidable and B ≤P A means A is undecidable
- If B∈ undecidable and A ≤P B No inference
The problems mentioned in the question are:
CLIQUE
A clique in a graph G is a complete subgraph of G; that is, it is a subset S of the vertices such that every two vertices in S are connected by an edge in G.
The clique decision problem is NP-complete.
3 SAT
(x1∨x2∨x3) ∧ (x4∨x5∨x6) … strict from of Boolean expression in which each clause should contain three literal connected by AND function and all clauses are connected by OR function. This problem search for a set of values of literals such that the Boolean expression will give 1 as output.
In simple way, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE
SAT is one of the first problems that was proven to be NP-complete.
So option (A) matches with rule 3 and 4.
We infer clique is NP and 3 SAt is NP hard
Vertex Problem
A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph. Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.
Vertex Cover Problem is a known NP Complete problem
So option (B) also matches with rule 3 and 4.
We infer clique is NP and vertex problem is NP hard
subset sum
The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?
The problem is NP-complete.
So option (C) matches with rule 3 and 4.
We infer clique is NP and Subset problem is NP hard
None of the options proves Clique problem is NP Hard.
So answer Must be D
