NP-complete facts for kids

An NP problem is an algorithmic problem such that if you have a case of the problem of size , the number of steps needed to check the answer is smaller than the value of some polynomial in . It doesn't mean one can find an answer in the polynomial number of steps, only check it.

An NP-complete problem is an NP problem such that if one could find answers to that problem in polynomial number of steps, one could also find answers to all NP problems in polynomial number of steps. This makes NP-complete decision problems the hardest problems in NP (they are NP-hard). People spent lots of time looking for algorithms that finds answers to some NP-complete problem in polynomial number of steps, but have not found any. Because of this, if someone shows a problem to be NP-complete, it is not likely that there is an algorithm solving it in polynomial number of steps.

The unsolved problem P = NP asks whether polynomial time algorithms actually exist for NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case.

The Travelling salesman problem is an NP-Complete problem.

See also

In Spanish: NP-completo para niños