Np complete what is

It is not intended to be an exact definition, but should help you to understand the concept. When you measure how long a program takes to run when it is given more and more difficult problems such as sorting a list of 10 items, 20 items, 30 items etc you can plot the times and come up with a function. But if the time goes up exponentially or factorially, or something that exceeds what a polynomial can do, it is NOT in "P" it is not solvable in "Polynomial" time.

P : can be solved in P olynomial time. How long it takes is defined by a polynomial. Now, the "N" in "NP" refers to the fact that you are not bound by the normal way a computer works, which is step-by-step.

The "N" actually stands for "Non-deterministic". This means that you are dealing with an amazing kind of computer that can run things simultaneously or could somehow guess the right way to do things, or something like that. So this "N" computer can solve lots more problems in "P" time - for example it can just clone copies of itself when needed. It is not a Super Computer they are just very fast normal computers , it is really a "Non-deterministic" computer, but I am calling it an Amazing Computer to give you the idea!

Conversely if everything in NP is easy, those problems are easy. So if we believe that P and NP are unequal, and we prove that some problem is NP-complete, we should believe that it doesn't have a fast algorithm.

So the theory of NP-completeness turns out to be a good way of showing that a problem is likely to be hard, because it applies to a lot of problems. But there are problems that are in NP, not known to be in P, and not likely to be NP-complete; for instance the code-breaking example I gave earlier.

There are several minor variations of this definition depending on the detailed meaning of "small" -- it may be a polynomial number of calls, a fixed constant number, or just one call.

So "easier" in this context means that if one problem can be solved in polynomial time, so can the other.

As an example, consider the Hamiltonian cycle problem. Does a given graph have a cycle visiting each vertex exactly once? Here's a solution, using longest path as a subroutine:. As a second example, consider a polynomial time problem such as the minimum spanning tree. We don't actually have to call the subroutine, or we can call it and ignore its results. This seems like a very strong definition. Why should there be a problem that closely related to all the different problems in NP? We prove this by example.

One NP-complete problem can be found by modifying the halting problem which without modification is undecidable. To be precise, this needs some more careful definition: what language is X written in? What constitutes a single step? Also for technical reasons K should be specified in unary notation, so that the length of that part of the input is K itself rather than O log K. For reasonable ways of filling in the details, this is in NP: to test if data is a correct solution, just simulate the program for K steps.

This takes time polynomial in K and in the length of program. Here's one point at which we need to be careful: the program can not perform unreasonable operations such as arithmetic on very large integers, because then we wouldn't be able to simulate it quickly enough.

To finish the proof that this is NP-complete, we need to show that it's harder than anything else in NP. Suppose we have a problem A in NP. This means that we can write a program PA that tests solutions to A, and halts within polynomial time p n with a yes or no answer depending on whether the given solution is really a solution to the given problem.

We can then easily form a modified program PA' to enter an infinite loop whenever it would halt with a no answer. If we could solve bounded halting, we could solve A by passing PA' and p n as arguments to a subroutine for bounded halting. But this argument works for every problem in NP, so bounded halting is NP-complete.

Most proofs of NP-completeness don't look like the one above; it would be too difficult to prove anything else that way. Recall that these relations are defined in terms of the existence of an algorithm that calls subroutines.

Given an algorithm that solves A with a subroutine for B, and an algorithm that solves B with a subroutine for C, we can just use the second algorithm to expand the subroutine calls of the first algorithm, and get an algorithm that solves A with a subroutine for C. In practice that's how we prove NP-completeness: We start with one specific problem that we prove NP-complete, and we then prove that it's easier than lots of others which must therefore also be NP-complete.

Starting from the bounded halting problem we can show that it's reducible to a problem of simulating circuits we know that computers can be built out of circuits, so any problem involving simulating computers can be translated to one about simulating circuits. See also NP-hard , P. Other well-known NP-complete problems are satisfiability SAT , traveling salesman , the bin packing problem , and the knapsack problem. Strictly the related decision problems are NP-complete.

History, definitions, examples, etc.