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 Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+10 votes

Which of the following statements are **TRUE**?

- The problem of determining whether there exists a cycle in an undirected graph is in $P$.
- The problem of determining whether there exists a cycle in an undirected graph is in $NP$.
- If a problem A is $NP-Complete$, there exists a non-deterministic polynomial time algorithm to solve $A$

- 1, 2 and 3
- 1 and 2 only
- 2 and 3 only
- 1 and 3 only

+20 votes

Best answer

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

Ref: http://www.geeksforgeeks.org/detect-cycle-undirected-graph/

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.

0

** there is Non-deterministic Turing machine** which solve in polynomial time?

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 449
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,499 questions

42,767 answers

121,499 comments

42,151 users