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

+21 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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,558 answers

146,290 comments

62,306 users