1.2k 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$

1. 1, 2 and 3
2. 1 and 2 only
3. 2 and 3 only
4. 1 and 3 only
edited | 1.2k 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.

edited by
0

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?

+1

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."

0
Yes, more precisely non deterministic halting TM I guess.