What does NP mean?

Complexity classes - P, NP, NP-hard, NP-complete

In theoretical computer science, problems can be divided into complexity classes. Since you only get to know P, NP, NP-hard and NP-complete in the lecture, I limit this contribution to these classes as well. Here you can find an overview of the other classes Link. However, these are sufficient for the beginning 😉

introduction

Problems in this case are tasks that a computer can delete, e.g. calculations. A modern computer has done most of the calculations in milliseconds. However, there are also problems that can never actually be solved by a computer, e.g. the holding problem. Then there are problems that become so difficult that a normal computer can never solve them in an acceptable time. To solve a problem one uses the Turing machine or creates an algorithm that can solve it. If you can build a Turing machine, the problem can definitely be solved.

P.

The complexity class P includes all problems in polynomial time are solvable. If one can build a deterministic Turing machine that solves the problem, it is in P. A deterministic TM can do everything a modern computer can do.

NP

The complexity class NP includes all problems from P plus further problems that cannot be solved in polynomial time. NP problems can only be solved in an acceptable time with a nondeterministic Turing machine. A nondeterministic Turing machine “advises” a possible solution to the problem and only polynomial time is needed to check the solution. Since a computer can only work deterministically and a Turing machine only exists theoretically, one has not gained much. However, it has not yet been proven that P ≠ NP. That means, it could be that you can write an algorithm for a NP problem, but no one has done it yet.

NP-hard

A problem that is NP-hard, either so difficult that it cannot be solved at all, or it is one of the most difficult problems in NP. If it is in NP, it means that all other problems from NP can be reduced in polynomial time to the NP-hard problem. Example: the holding problem is NP-hard because it cannot be solved at all. So it is outside of NP.

An NP-hard problem that is also in NP is called NP-complete. As already mentioned, all other problems can be reduced to this. An example of this is SAT (satisfiability problem)