# NP Problem Stepwise

Hey, Let discuss this in stepwise firstly there r 2 kinds of computational m/cs

**1.Deterministic:**

Computers which we are using with performance and parallelism limitations

**2.Non-Deterministic:**

Computer which we wish we could have that can have tremendous parallelism

Now **what is problem**?

Ans: Problem is to** decision problem** which gives answer in Yes/No..

**P-Problems:**

Problems which could be solved in **Polynomial time by a deterministic m/c.**

**NP-Problem:**

Which could be solved in **polynomial time by a non deterministic m/c.**

**NP-Complete Theory:**

NP-complete problems are defined recursively,a problem is NP-complete problem

if:

1.It is a NP-problem.

2.It is reducible to an NP-complete problem in a polynomial time.

now question arises

Questionn: What is the** first**** NP-complete problem.?**

Answer : boolean satisfiability problem was first NP-complete problem proposed **by Steve Cook.**

Question: How to prove **given problem is NP-complete or not?**

Answer: Now to prove that any NP problem is NP-complete, we need to prove that, it is reducible in polynomial time to boolean satisfiability problem.

**Boolean Satisfiability Problem:**

It is the problem to find of whether given boolean equation is true or false.

**NP-Hard:**

This is a problem to which a NP- complete problem is polynomial time turing reducible.

i.e If a problem X in NP-complete is polynomial time turing reducible to problem Y, problem Y is NP-hard problem.

**Turing Reduction:**

It is nothing but an algorithm which solves problem A when it knows how to solve problem B by converting A into B. That is all algorithm can be applied on B by inserting

reduction algorithm in between.

Hi, i have reading out and i will definitely bookmarrk your site, just wanted to say i liked this article.

Good one…some more elaboration will be more helpful..:)

Hi,

Thanks for this useful blog. Now I got idea for my thesis. It helps me a lot.