{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.manongdao.com/data/attach/logo/logo.png', '推荐 做自己的国王 的问题《What are NP problems?》','https://www.manongdao.com/q-885754.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
I read the article on wikipedia but could not understand what exactly are NP problems. Can anyone tell me about them and also what is relation of them with P Problems?
相关问题
- Calculating the complexity of an algorithm with 3
- Finding the minimum in an unsorted array in logari
- Complexity of STL max_element
- Is the complexity of unordered_set::find predictab
- Shuffling a sorted array
相关文章
- What is the complexity of bisect algorithm?
- How to measure complexity of a string?
- Searching strings with . wildcard
- why O(2n^2) and O(100 n^2) same as O(n^2) in algor
- Merge sort worst case running time for lexicograph
- Sorting nearly sorted array with O(n*Log(K)) compl
- GCD algorithms for a large integers
- 3D Connected Points Labeling based on Euclidean di
NP problems are problems that given a proposed solution, you can verify the solution in a polynomial time. For example, if you have a list of University courses and need to create a schedule so that courses won't conflict, it would be a really difficult task (complexity-wise). However, given a proposed schedule, you can easily verify its correctness.
Another important example from the field of encryption: given a number which is the result of multiplying two very large prime numbers, it's very difficult to find those primes based only on the result. However, given two numbers, it's very easy to check the solution (multiply them, compare).
I have intentionally chose examples that are in NP and not in P (i.e. problem that are hard to find the solution for) so you can understand the difference. All problems that are easy to solve, are also easy to verify - just solve and compare. That is, P is a subset of NP.
Not really an answer, because Piccolo's link is more useful, but a HP researcher claims having proven P != NP, here is the paper.
www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
It was not accepted yet, but I wish him good luck for the 1M$.