https://tcs.nju.edu.cn/wiki/api.php?action=feedcontributions&feedformat=atom&user=2.223.170.161TCS Wiki - User contributions [en]2026-05-04T22:08:04ZUser contributionsMediaWiki 1.45.3https://tcs.nju.edu.cn/wiki/index.php?title=NP-complete&diff=7738NP-complete2016-12-30T12:39:48Z<p>2.223.170.161: Added NP-hardness link</p>
<hr />
<div>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 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. <br />
<br />
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 algorithm that finds answers to some NP-complete problem in polynomial number of steps, but haven't 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.<br />
<br />
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.<br />
<br />
The [[Travelling salesman problem]] is an NP-Complete problem.<br />
<br />
{{math-stub}}<br />
<br />
[[Category:Theoretical computer science]]</div>2.223.170.161