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