NP Problem Stepwise

Hey, Let discuss this in stepwise firstly there r 2 kinds of computational m/cs
Computers which we are using with performance and parallelism limitations

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

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

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


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



  1. sibel says

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

  2. sawan says

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

  3. Nisha says

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

Leave A Reply

Your email address will not be published.