Test: Dynamic Programming, P & NP Concepts- 2 - Computer Science Engineering (CSE) MCQ

In a complete graph total no of edges is

Time complexity of Bellman-Ford algo for a graph having n vertices and m edges = O(nm) for a complete graph time complexity

Ackermann’s function has exponential time complexity,

1. By depth first search we can find whether there exits a cycle in an undirected graph in O(n²) times so it is P problem.
2. As so this problem will also be considered as NP problem.
3. This is the definition of NP-complete so it is trivially true.

Given Q₁ ≤ 3-SAT and 3-SAT ≤ Q₂ 3-SAT is NP- complete.
∴ It is NP as well as NP-hard.
  is NP-problem   3-SAT ≤ Q₂ and 3-SAT is NP-hard ⇒ Q₂ is NP- hard problem.
So the strongest statements is Q₁ is in NP and Q₂ is NP-hard.

if L₁ ∈ P we cannot say anything about L₂ from 
Since we cannot say anything about L₂ therefore we cannot say anything about L₃ either from 
So Statement III is false.
IV. If L₄∈ P, then L₁ ∈ P and L₃ ∈ P is true.
If L₄ ∈ P then fromwe can get that L₂∈ P.
and from  we can now get that  L₃ ∈ P 
also from we can get that L₁ ∈ P
So Statement IV is true.