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** e**xample::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