P vs NP


P: problems quickly solvable

NP: problems quickly checkable

Quick means the existence of an algorithm solving the task that runs in polynomial time.

If it turned out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify.

Many of the problems in NP have the extra property that a fast solution to any one of them could be used to build a quick solution to any other problem in NP, a property called NP-completeness. An NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.

NP-hard problems are those at least as hard as NP problems.

Last Article Next article

Comment 评论



Share 分享

New Users 最新加入

  • hokurikustr

  • refrain

  • 鑫鑫

New comments 最新评论

test123: aasdas Details Apr 13 16:39
admin: Thanks! Details Apr 09 11:46
admin: Google map api Details Apr 09 11:46
lqj12: cooooooooool Details Apr 08 21:34
Yunhan Huang: 这个功能是如何实现的? Details Apr 08 13:23