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.

Home / Engineering / Theory of Computation / Question

Mr. Dubey • 51.17K Points
Coach

Q.) 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.

(A) 1, 2 and 3

(B) 1 and 2 only

(D) 1 and 3 only

Correct answer : Option (A) - 1, 2 and 3

Discusssion

Related MCQs on Theory of Computation

Q. In the network HTTP resources are located by

Q. Find the maximum value output assuming items to be divisible and nondivisible respectively.

Q. Select the command which is used to pause execution until the page is loaded completely

Q. A use-case____________ represents how a use case will be implemented in terms of collaborating objects.

Q. The reason for the implementation of the cache memory is ________

Q. Which of the following statement is true?

Q. True or False: Dropout is computationally expensive technique w.r.t. bagging

Q. script is run for successful login

Q. In web mining, is used to find natural groupings of users, pages, etc.

Q. An 8-bit binary number is input to an odd parity generator. The parity bit will equal 1 only if .