The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 votes

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
asked in Theory of Computation by Veteran (368k points)
edited by | 1.5k views

1 Answer

+21 votes
Best answer

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.  

answered by Veteran (368k points)
edited by

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.
to find the total no of cycle in undirected graph then what would be answer?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,253 questions
49,750 answers
65,847 users