41–50 of 60 posts
Earlier quoted context omitted.
See: https://en.wikipedia.org/wiki/NP-intermediate
Great link I particularly like the part that says, "P = NP if and only if NPI is empty." seems to indicate that if there are any NP Intermediate problems P would be proven not to equal NP.
Case 1, it's proved that P = NP, and the complexity of solving an NP problem is N^1000. Case 2, it's proved that P != NP, and the complexity of solving an NP problem is N^log log log log N.
In both cases, the result is technically correct (case 1 is polynomial, case 2 is exponential), but from a practical standpoint this proof that P != NP is much more world changing than this proof that P = NP. For example, you'd have to have a problem size that's measured in hundreds of digits before even getting to N^3!
I definitely got a sense of mathematical awe out of that. Thanks for sharing. I'm always impressed when I see someone who can communicate ideas, especially complex scientific concepts, clearly and effectively, using analogies in a proper way that doesn't just overwhelm the viewer (as a lot of popsci stuff does). It's a talent I know that I need to work on; as a fledgling academic attempting to write papers clearly I…
http://betterexplained.com/articles/adept-method/
It's by the author of better explained - a really great math teaching site.
Reddit's thread: https://www.reddit.com/r/programming/comments/372634/the_n_v... The video is very well structured and goes from very basic explanations of the concept of complexity up to the different classes of complexities.
My expectation, however, is that either P!=NP or if it isn't, we will probably find out because some day, some guy wanted his program to run a little faster and he just happens to solve A NP-complete problem in polynomial time, therefore collapsing NP into P (remember, solving one of them solves all of them). Who knows, maybe the source code for some random Indie game someone programmed in his basement already contains the solution and nobody has noticed, a bit like back in the day with quakes "fast-inverse square root", which was so great it's now integral part of graphics computing. And we only noticed because the water looked so great.
https://www.reddit.com/r/programming/comments/372634/the_n_v...
It's nice and simple to talk like that, but I don't think it's particularly useful or helpful.
For example, there is a linear time algorithm for deciding whether two planar graphs are isomorphic (Hopcroft,Wong 1974). But the constant of the asymptotic time bound of their algorithm so large that it was not useful or practical (see end of abstract, http://dl.acm.org/citation.cfm?id=803896)
Only in 2004 did Kukluk, Holder, Cook publish a quadratic time algorithm, "suitable for practical implementation." http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf
More such examples are listed at "Polynomial-time algorithms with huge exponent/constant," http://cstheory.stackexchange.com/questions/6660/polynomial-...
The video is misleading when it spreads the idea that "polynomial time" equals "practical," or "fast". It's nice and simple to talk like that, but I don't think it's particularly useful or helpful. For example, there is a linear time algorithm for deciding whether two planar graphs are isomorphic (Hopcroft,Wong 1974). But the constant of the asymptotic time bound of their algorithm so large that it was not useful or…
To start, yes, I do like the question of P versus NP and regard it as a very important research question. My reaction to the video lecture: Wow. Amazing. Gee whiz. P versus NP. What a biggie! Or is it? There does seem to be a little, tiny, itsy, bitsy point where the lecture went off the track: The lecture gave a big list of some of the amazing things we could do if we could prove that P = NP. Some of the items on th…
>By the way, Mother Nature does protein folding, right?
Yes, but it does it directly without simulating any models of itself. As soon as you add the indirection and abstraction needed for human communication, you can't use those methods.
That's like saying "Usain Bolt can run fast, so you should be able to run fast just by pretending to be him." You can't be nature by pretending to act like it in an abstract model. I can't solve a protein folding problem by simply realizing that my body already folds proteins. That has nothing to do with the mental models of protein folding we use.
What about the problem of a solution to P and NP being ambiguous for practical uses? I read this argument somewhere, but can't find it now: Case 1, it's proved that P = NP, and the complexity of solving an NP problem is N^1000. Case 2, it's proved that P != NP, and the complexity of solving an NP problem is N^log log log log N. In both cases, the result is technically correct (case 1 is polynomial, case 2 is exponent…
Similar arguments apply to case 1. (We know quite a bit about how a proof of NP ?= P could _not_ look like, because people already proved that certain strategies for a proof don't work. I am not sure if we can already rule out N^log log log log N, but it wouldn't surprise me.)
Lets say I want to solve a problem, but I have no idea if it is solvable in polynomial time. Is there a website or a book where I can look that up?
Remember quantum computing ? a lot of NP problems will become P
No, they'll become a part of BQP (or rather are already). P is defined as the class of problems decidable in polynomial time on a classical Turing machine. P doesn't change with the advent of quantum computers. Also it is suspected that BQP \not \subset NP, i.e. there are problems in BQP that might not be in NP.