4 ms·
To understand the P = NP stuff, you first need to understand what people mean by "P" and "NP". "P" refers to problems that can be solved in polynomial time. Th
by lacker 13y ago
To understand the P = NP stuff, you first need to understand what people mean by "P" and "NP".
"P" refers to problems that can be solved in polynomial time. This includes almost all of the normal algorithms that you use in everyday programming, like sorting a list or using a hash table.
"NP" refers to problems whose answers can be checked in polynomial time. This is kind of a weird group of problems. Generally an NP problem will be phrased as, "Can you find a solution to this formula?" Like, can you color a given graph using X colors without giving two adjacent nodes the same color?
So. The "P = NP" question is whether these classes of problem are actually the same. You can generally solve a find-the-solution-to-this-formula problem by checking all the possible solutions. That takes exponential time, though. The "P = NP?" question asks, is there a general way of solving these problems faster?
Most people who have an opinion suspect that the answer is no. That P is not NP, and that there is no fast way to solve general formulas. However, it's really hard to prove that writing a particular program is impossible, and nobody has proven that P != NP.
It's a fairly complicated problem definition, so I wouldn't assume that all these folks are BSing you. It's just tricky to explain because it depends on a lot of other knowledge.
- orionblastar 13y agoHow does one learn this other knowledge when they cannot afford tuition at a high priced university anymore but has a university degree, just not a graduate degree?
- tptacek 13y agoWikipedia is a good start here.
- orionblastar 13y agoWikipedia is not a good start for me because I find the articles there on the subjects involved very confusing. It is like they are writing in bad grammar with poor logic and cannot follow any sort of logic I understand. Anything else to use? Don't get me wrong I used to be big on Wikipedia, but over the years it has gotten worse, using unverified sources, taking things for granted without references and citations, claiming it is 'general knowledge' and does not need verification and citations. Every since 2007 they allowed people with fake degrees to cook the facts and statements in Wikipedia articles and now they are mostly nonsense and poor logic and hard to understand for me. http://www.telegraph.co.uk/news/1544737/Fake-Wikipedia-prof-altered-20000-entries.html http://www.telegraph.co.uk/news/1544737/Fake-Wikipedia-prof-...
- dangrossman 13y agoYou look up the course website at a decent university, and buy the same textbook they require students read, then read it yourself. Lecture notes and slides can typically be found the same way. This is the book for this topic: http://mitpress.mit.edu/books/introduction-algorithms http://mitpress.mit.edu/books/introduction-algorithms
- orionblastar 13y agoThank you very much, this is the best advice I could be given here.