What is NP-complete?
{{no sources|date=February 2024}} An NP problem is an [[algorithm]]ic problem such that if you have a case of the [[problem]] of size <math>n</math>, the number of [[Step|steps]] needed to check the [[answer]] is smaller than the value of some [[polynomial]] in <math>n</math>. 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-hardness|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 versus NP|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. {{math-stub}} [[Category:Theoretical computer science]]