## UnkleRhaukus one year ago Explain what is meant by an NP-complete problem.

1. amoodarya
2. UnkleRhaukus

i still don't understand it

3. Kainui

4. Kainui
5. Mimi_x3

NP - complete - hamilton path - sudoku cannot be solved in polynomial time but then u can find the answer to it

6. Mimi_x3

I had to do this for my one assignments http://en.wikipedia.org/wiki/Travelling_salesman_problem

7. anonymous

P and NP isn't too hard to understand.

8. anonymous

P just means that a deterministic Turing machine can solve it in a $$\bf P$$olynomial number of steps. NP means a $$\bf N$$on-deterministic Turing machine can solve it in a $$\bf P$$olynomial number of steps. A Turing machine is an infinitely long band of tape and a cursor with a counter. The tape consists of frames and each frame has a symbol. The symbol gives the cursor an instruction, such as move left or right, change the counter value, and write a symbol down on another frame. A deterministic Turing machine has at most one instruction in each frame, while a non-deterministic Turing machine can have multiple instructions in each frame. When the cursor hits a frame with $$n$$ instructions, then it splits into $$n$$ different cursors and they run each instruction independently of each other. You can think of a deterministic Turing machine as our current computers if they were to have infinite memory. When we're talking about these things, generally we're ignoring any limitations in RAM or drive. The main difference between deterministic and non-deterministic is that deterministic must commit to a single choice, while a non-deterministic execute all choices simultaneously to solve a problem. The both machines have the same computing power, which is to say that if either one of them can solve a computing problem, both of them can. The issue is how many steps it would take to solve the problem. If we try to emulate a non-deterministic Turing machine, we have to keep a collection to hold the positions and counters of each cursor, and we would still have to execute their operations sequentially. It would be exponential increase in the number of steps. In general, implementing problems on the theoretical Turing machines is a bit difficult, so instead what we tend to do is to use an algorithm to solve another algorithm and vise versa. For example, the min operation gets the smallest element in a collection. The sort operation puts all elements in a collection in order. We can utilize min to solve sort by finding the min element, removing it, and putting it into a new sorted collection. We could repeat this until the collection was sorted. We would only need to repeat this process $$n$$ times (the size of the collection), which is a polynomial. Since the composition of a polynomial with a polynomial is still a polynomial, then we know that if min is a P problem, then sort, which can be solved using min a polynomial number of times, must also be a P problem. In fact we would say that sort is no harder than min in terms of polynomial steps. We say a problem is NP Hard if it can be used a polynomial number of times to solve any NP problem . Thus we can say that every NP problem is no harder than every NP Hard problem. The 'no harder than' designation can be shown the same way I showed that sort is no harder than min. Also since it is a transitive relation, we really only have to solve the "hardest" NP problems using the NP Hard problem to show it is NP hard. The "hardest" NP problems are what we would call NP Complete problems. They are problems which are both NP Hard and NP. Suppose problem $$A$$ is NP, and you're not sure about problem $$B$$. If you can show that $$A$$ is no harder than $$B$$, then you know $$B$$ is NP Hard. If you can show that $$B$$ is no harder than $$A$$ as well, then you've known that $$B$$ is NP. Showing both would mean $$B$$ would be NP Complete. We know NP problems can be used to solve P problems in a polynomial number of steps, which means that P problems are also NP problems. So far, no one has ever been able to solve an NP Complete problem using any P problem a polynomial number of times. Therefore we don't know if NP Complete is no harder than P or not. If it were true, then that would mean P = NP = NP Complete. All of our current methods for solving NP Complete problems require an exponential number of steps, but if someone showed P = NP they could all be solved in a polynomial number of steps. Breaking encryption is an NP Complete problem. Just to keep some things in mind: P is no harder than NP, and P is a subset of NP. NP is no harder than NP Hard, and NP Complete is a subset of NP and NP Hard. So far, it seems that NP Complete is harder than P which means P $$\neq$$ NP, but it has yet to be proven whether or not P and NP Complete are equivalent (neither is harder than the other).

9. anonymous

It seems that @Lyrae was saying that NP are the problems that can be verified in polynomial time. That is definitely an interesting way of looking at it, but not quite what the definition says. I'm not sure what formal definition of verifying a problem would entail, so I don't know if verification and solving with a non-deterministic machine are interchangeable criterion in the definition. The one way to understand a deterministic versus non-deterministic machine is to look at a tree. |dw:1433108516731:dw| Suppose we want to find $$x$$ in the tree. A deterministic algorithm must traverse one branch at a time, and in the worse case it makes $$3 + 9 = 12$$ traversals in $$12$$ steps. A non-deterministic algorithm can take all branches simultaneously, and so it makes $$12$$ traversals in $$1+1=2$$ steps. To relate this to P and NP, we could make the depth of the tree be the polynomial $$f(n)$$ with highest degree $$d$$. We can suppose that no node has more than $$k$$ children. For a deterministic machine, in the worst case it will take us:$\sum_{i=1}^{f(n)}k^i = \frac{k(1-k^{f(n)})}{1-k} = O(k^{n^d})$The non-deterministic machine in the worst case will take us: $f(n) = O(n^d)$

10. UnkleRhaukus

Thank y'all for these excellent responses! I've written the below: ___ A decision problem is one in which there is a definite boolean answer; true (1), or false (0). A decision problem is said to be in P, if it is know that a solution can be found deterministically in the order of polynomial time. Such a solution can be obviously also be checked in a such order of time. A superset of P problems, is NP problems. These are decision problems that for which there also exists a polynomially ordered verification procedure for a potential solution, but that a method for finding such a solution is not know to be findable (deterministically) within polynomial time. If a solution to any particular NP problem becomes know to be findable in polynomial time, then that problem becomes know to be also in P. An NP-complete problem is the set of problems, including NP (and thus P), of which again a polynomially ordered verification procedure exists, but to the extent that which it is as difficult as a problem can be, and still have such a verification process. Thus an NP-complete problem, can be shown to be at least as difficult, as all other NP problems. Thus, if a polynomially ordered general solution to any NP-complete problem was found, then all NP problems would become solvable by a reduction; the sets would collapse to simply P. ___ Have I got this all right? have I missed anything important? is it clear?

11. Lyrae

There are actually several definitions of NP. Formally NP is defined as $NP = \bigcup_{k \in \mathbb{N}} NTIME(n^k)$Which approximately reads as the union of problems solvable in $$O(n^k)$$ for any natural number k given input size n (ie. all problems solvable in polynomial time) by a non-deterministic TM. The other equivalent definition uses verifiers instead. Wikipedia provides a fairly good explanation on this http://en.wikipedia.org/wiki/NP_%28complexity%29#Verifier-based_definition To solve a problem in NP you can hence non-deterministicly select input (certificates) and run them through its verifier in P. This is equal to the first definition.

12. Kainui

$$\color{blue}{\text{Originally Posted by}}$$ @wio For example, the min operation gets the smallest element in a collection. The sort operation puts all elements in a collection in order. We can utilize min to solve sort by finding the min element, removing it, and putting it into a new sorted collection. We could repeat this until the collection was sorted. We would only need to repeat this process $$n$$ times (the size of the collection), which is a polynomial. $$\color{blue}{\text{End of Quote}}$$ For some reason I really enjoyed reading this paragraph most of all. It sort of opens my eyes to the concept that we can literally build different algorithms out of others or something which I guess I wasn't explicitly in the frame of mind before. It makes me realize the "mix and match" nature of specifying things a lot better I suppose.

13. UnkleRhaukus

Thank you everyone, you have all helped me.