1k views

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     (C) 2 and 3 only     (D) 1 and 3 only

recategorized | 1k views

Cycle detection is graph is in P as it can be done using a graph traversal (O(V+E))

If a problem is in P then it is also in NP as P is a subset of NP. So, both 1 and 2 are TRUE.

Statement 3 is also true as NP-Complete requires a problem to be in NP and for any problem in NP, we have a non-deterministic polynomial time algorithm.

So, answer is A- 1, 2 and 3 are TRUE.

selected

Is problem solved by NON-deterministic polynomial time algorithm  is same as saying that there is Non-deterministic Turing machine which solve in polynomial time?

the formal definition of NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. This second definition is the basis for the abbreviation NP, which stands for "nondeterministic,polynomial time."

Yes, more precisely non deterministic halting TM I guess.