Algorithms MCQ - Algorithm Design Techniques

61 Which of the following statements are TRUE?
1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there exists a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

1. We can use “Depth First Search” Algorithm, to check it there is a cycle is an undirected graph. I t we encounter any “back edge” in “Depth first search” then given undirected graph has a cycle. Also, If there is a cycle in the Undirected graph, we must encounter a “back edge” in DFS. And, DFS can be done in O(| E| + | V| ) time for graph G = (V, E). So, it can is in F.
2. P ≤ NP, So, it is also in NP.
3. NP - complete problem A ∈ NP. By, Definition Every problem in NP can be solved in polynomial time using non-deterministic turing machine.
So, Answer is (A) i.e. 1, 2, and 3 are true.

62 Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the foliowing represents the correct Venn diagram of the complexity classes P, NP and NP Complete(NPC)?

The most important open question in complexity t heor y is whether the P = NP, which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems (since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P = NP = NP-Complete.

63 Consider the decision problem 2CNFSAT defined as follows:
{Φ|Φ is a satisfiable propositional formula in CNF with at most two literals per clause}
For example, Φ = (x₁ ∨ x₂) ∧ (x₁ ∨ x₃) ∧ (x₂ ∨ x₄) is a Boolean formula and it is in 2CNFSAT. The" decision problem 2CNFSAT is

2CNF SAT can be solvable in polynomial time by reduction to directed graph reach ability.

64 Consider two decision problems Q₁, Q₂ such that Q₁ reduces in polynomial time to 3-SAT and 3- SAT reduces in polynomial time to Q₂. Then which one of the following is consistent with the above statement?

Q₁ is in NP and Q₂ is in NP-hard

65 Language L₁ is polynomial time reducible to language L₂ Language L₃ is polynomial time reducible to L₂, which in turn is polynomial time reducible to language L₄. Which of the following is/are True?
I. If L₄ ∈ P, L₂ ∈ P
II. If L₁ ∈ P or L₃ ∈ P, then L₂ ∈ P
III.L₁ ∈ P or if and only if L₃ ∈ P
IV. If L₄ ∈ P then L₁ ∈ P, then L₃ ∈ P

L₂ ≤ pL₄
L₁ ≤ pL₂
If L₄ ∈ P
then L₂ ∈ P
L₁ ∈ P,