4 ms·
This video by Mike Sipser (http://www.youtube.com/watch?v=msp2y_Y5MLE http://www.youtube.com/watch?v=msp2y_Y5MLE) might help you. It might be long, but you need
by sold 13y ago
This video by Mike Sipser (http://www.youtube.com/watch?v=msp2y_Y5MLE http://www.youtube.com/watch?v=msp2y_Y5MLE) might help you. It might be long, but you need to spend a longer time if you are confused.
First of all, P=NP is not a "theory"; it's a _question_. We do not know whether the answer is "yes" or "no"; most experts suspect that the answer is "no", i.e. P is not NP. There were attempts to prove it both ways, none successful or even remotely close. The theory encompassing the question is called computational complexity. It is a relatively new field (foundation is often taken to be ~1965), and many questions are open. However, we do make progress and each year there are breakthroughs. People hope to solve it some day - history shows that many open problems in mathematics resisted for long, but they were finally solved after centuries of thinking.
"I want it in simple words so it is easy to understand"
The definition of P and NP uses things such as "decision problem", "polynomial running time", "nondeterministic" algorithm or Turing machine etc. You need effort to understand them. You have to read about those prerequisites, internalize them in your mind, and only then it will become understandable. "Simple words" won't help in overcoming that. You might have heard lots of intuitive musings about P=NP and are not satisfied. The only cure is rigor.
I hope you will not take my words as condescending, but it is not helpful when you say "it makes no sense to me"; it's like someone told you "the program does not work", how are you going to help that person? You need to have a leg to stand on. What you do understand from explanations, what do you not understand from them?
- orionblastar 13y agoMost likely I used a poor choice of words, more like I don't understand it. I want to know more, but my knowledge is limited and nobody seems to be able to explain it to me in a way that I can understand. In all honest I don't understand any of it. When I ask about it, instead of explaining it to me, most people just link to the Wikipedia article, instead of using their own words. I've read the Wikipedia article, and I don't understand any of it. My perception is that it does not follow any logic or reason that I understand, there is nothing that I can understand from it, and I don't want to be ignorant on the subject, I want to learn it.
- sold 13y agoYou have major gaps in knowledge (for example, in this thread you effectively said you don't know asymptotic analysis of algorithms). Start with something simpler - check what is a polynomial, big O, a Turing machine etc. Backtrack to simple things. Be persistent. Search for a textbook like Cormen's Introduction to Algorithms or Hopcroft/Ullman's Introduction to Automata Theory, and slowly read it. You can't be helped by using "my own words"; my own word for "polynomial" is "polynomial", it is commonly accepted and understood by the computer science community. It can't be dumbed down.
- orionblastar 13y agoI guess I got books to read then. Thank you.