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.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,996 questions

45,492 answers

131,517 comments

48,592 users