The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1.7k 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
asked in Theory of Computation by Veteran (408k points)
edited by | 1.7k views
0

lets understand some term 

P = the set of problems that are solvable in polynomial time by a Deterministic Turing Machine.

LIKE binary search ,linear search,breadth first search,depth search,chekhing whether cycle exist in a graph(this is algo behind  prims algorithm to find minimum spanning tree to detect  cycle when we add an edge .its time complexty = O(V+E))  

not polonomial time algo example::sum of subset, 3 sat etc

NP = the set of decision problems (answer is either yes or no) that are solvable in nondeterministic polynomial time i.e can be solved in polynomial time by a Nondeterministic Turing Machine.

Nondeterministic Turing Machine(NTM) — a branching machine. If many options for the next step of computation exists this machine can go down all of them at the same time. NTMs are capable of guessing the correct option out of polynomially many options in O(1) time.

Proving that A Problem X is NP-Complete:: it involves 2 steps. First we have to show that the problem belongs to NP and then we have to show it is NP-hard.

 

Step 1 — Showing X ∈ NP. find a nondeterministic algorithm for X.

Step 2 — Showing X is NP-hard. Reduce from a known NP-complete problem to X(like 3 SAT PROBLEM)

Given problem

option A.Cycle detect algo O(V+E)==P(correct it is polynomial)

option B.every P(Deterministic turing machine accepted) is also NP(non detrministc turing machine).(correct)

option C.Any problem comes in NP -complete when it 

         A.(above step1)  havinng a nondeterminstic polynomial time algo exist for that. (So Option C Is Correct)

         B. is  able to reduce that from some known NP complete problem

 

So option A

0

@sushmita @Ayush Upadhyaya NP, P in syllabus? 

0
No

1 Answer

+22 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.  

answered by Veteran (408k points)
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.
0
to find the total no of cycle in undirected graph then what would be answer?
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
49,548 questions
54,174 answers
187,484 comments
71,128 users