Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.
First what NP stands for : Non-deterministic Polynomial which is a generic term in the way the present day turing machine computers solve a given problem.
and NP complete problem is one which has been proved that it cannot be solved using present day computers. Meaning that present day computers may take years or in some cases (depending upon the input numbers), never.
an e.g is the travelling saleman problem (for large number of destination)'
A slightly different class of problems are NP hard problems. These are problems for which no algorithm has been found. But also they have not been proved as unsolvable.
P complete is quite the opposite , a problem proved solvable and an algorithm exists...
hope u got it ....
for details, you can look into books like "Introduction to Computation" by Michael Sipser.... "Introduction to Automata Theory, Languages, and Computation" by Hopcroft-Ullman (addison-wesley) ..
a more specific book on NP completeness wud b "Computers and Intractability: A Guide to NP-Completeness" by Garey and Johnson .... this book has numerous wonderful examples ...
NP Complete problems are those problems that cannot be solved in polynomial time, they need exponential.
NP hard problems are problems that no polynomial algorithm has been found yet
P goes for problems solved in polynomial time...
For the NP problems we have exact algorithms (take days or years) and heuristic algorithms for near-optimal solutions in microseconds (focus: they are non optima)
Ways of programming
Linear Programming
Integer Programming
Dynamic Programming
Quadratic
Mixed types
Go google and write Traveling Salesman problem and start from there...
Some books
Vasek Chvatal : Linear Programming
Lawler .. : Traveling Salesman Problem
Dimitris Bertsekas: Dynamic Programming and optimal control
Well ... a turing m/c is an imaginary m/c which can compute based on given steps. All of today's computers run on the principle of Turing m/c whose idea was conceived by the famous british mathematician Alan Turing in the 1930s.
Turing was trying to prove what a computer can solve. In general if a problem is not solvable by turing m/c, it can't be solved by today's computers and hence become NP complete problems. (what i mean by solving is that to find an algorithm running in polynomial time)
In simple terms turing machine, has a tape of infinite divided into cells. A header attached alongwith can read, write, move left/right. Turing proved with this simple machine and some combination of this machine, he proved the abilities and shortcomings of a computer (which was yet to be built during his times)
This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
By continuing to use this site, you are consenting to our use of cookies.
