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 struggle with it. Does it simply come with practice or are there resources anyone here can recommend for improving one's ability to make hard ideas understandable?
Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (correct me if I am wrong) a problem that can only be solved in factorial time on a Deterministic Turing Machine for example cannot be part of the class NP.
He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest. https://www.ibm.com/developerworks/community/blogs/jfp/entry...
As with writing in general, here's how I personally approach it:
1. Practice, practice, practice.
2. Find good examples (like this video) and try to extract and generalize the techniques that you think work really well.
and the last point which not everyone thinks of consciously:
3. Watch sports, read books, watch TV and movies, read the news, and go outside. When you must communicate by analogy, you need a broad pool of experiences to draw from so that you can match your audience.
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.
"Simplicity is the final achievement" -- Chopin, according to the video.
After a bunch of Googling the only source I can find for this is a 2007 religious apologetics book with no Amazon reviews. I can't even find a French version of the quote. Anyone know if it's legitimate? And a more interesting question: if no one has ever even reviewed this book, how is it all over the Internet as the source of this quote?
EDIT: Oops, looks like it is not religious apologetics. Still, I'm curious how a (presumably manufactured) quote like this spreads from such an obscure source.
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 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!
In practice we find that algorithms in P usually have small exponents. And thus P is a good shorthand for tractable. If case 2 happens, we'll have to change our shorthand to what we actually care about: tractability.
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.)
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 practical (see end of abstract, http://dl.acm.org/citation.cfm?id=803896)
I think the video addresses it in a fair and approachable manner. It makes it clear that the value is in scaling algorithms to larger inputs, and even shows so in a graph. When dealing with unbounded scaling, the constants typically do not matter.
This definitely stirred up some of the dust in my head that has settled since I took Algorithms in college. Specifically, I forgot about how different the world would be if P is actually NP. It's interesting to think about, kind of in the same vein as trying to comprehend the size of the universe.
NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input.
P = Set of problems for which we can find a solution in polynomial time in the length of the input.
Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.
My simplistic take away is it's an answer to this question about algorithms.
For a problem you can have a number of different algorithms to solve the problem. And a number of algorithms to check the solution to a problem. This is a point that is skipped over and trips lay people up because in school people are usually taught _the algorithm_ for solving a problem. But there are all sorts of ways to skin the cat mathematically. Some of these algorithms are great and some are 'bad'
Polynomial time algorithms are good. Ones that blow up exponentially are bad.
The question is, if you find a good polynomial time checking algorithm for a problem, does that mean there are polynomial time solving algorithms for that problem? Or not.
what we are concerned with here are two things, that becomes easier to explain as three things:
* the problem's class
* the algorithm.. or proof
* the size of the input
* the problem's class:
each problem has a corresponding class(i) determined by a universal set of rules based on current solving algorithms and how they react to different input
in a beautiful and approachable paper by richard karp titled: reducibility among combinatorial problems(ii); karp showed that the hardest problems, that seem unable to be solved in polynomial or subpolynomial time, called NP-Hard, are basically all the same problem viewed from different perspectives
karp develops reducibility, a process used to show that one can reduce any of his 21 chosen problems into any of the others through a specific tree of transformations he calls reductions
this set of problems that form the tree of reductions is called NP-Complete
i say it is approachable because this paper develops reducibility and as such lacks any assumption about the reader's previous knowledge
.
* the algorithm:
check out this chart(iii) that lists some time complexities, you will see polynomial,P, time about mid way through
polynomial time is 2^O(log n) or poly(n), that 'O()' syntax is something called big O, which is analogous to a sort of algorithmic measurement unit(iv) derived from number of necessary operations in relation to the size of the input
all algorithms before the polynomial time listing are sub polynomial time for any inputs and as such are classified as P
.
* the size of the input:
lots of np problems have algorithm solutions that can solve specific inputs in polynomial time
sometimes those inputs are small, or follow a specific pattern, but a general purpose algorithm, or a collection of specific algorithms that can be proved to cover all possible inputs, that runs in a reduced(v) complexity of polynomial or sub polynomial time is necessary to be classified P
one way to prove P=NP is to take one of karp's problems and develop an algorithm that satisfies the above stated requirements
once developed karp's reductions can be used on the algorithm to show that all NP-Complete problems are in P as well, therefore P=NP
Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.
I studied this topic mainly from Algorithms text by Kleinberg/Tardos[1]. Like everything else, if you interested in proving problems NPC, read few examples from book and practice some on your own. Proving problems NPC of some common problems isn't very hard once you get hang of it.
i talk about karp's paper: reducibility among combinatorial problems(i); in another thread
and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii)
do any of these examples explain the problem best for you?
can you write a program that will solve this question for you?
now change the values of the variables, increase the number of variables
does your algorithm still work on these other inputs?
can you rewrite the algorithm to give the correct answers for these other inputs?
can you develop enough coverage to prove all possible inputs return correct values?
if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm?
for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii)
this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21
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
that list were protein folding (to cure
cancer) and scheduling.
Right? Not so much:
If someone has an important problem in
scheduling, protein folding or any of the
NP-complete problems, bring forward that
actual, specific, instance of the real
problem.
Why? Because there's no proof and little
evidence that finding a solution will be
too difficult for "current computers".
To this claim I can hear the complaint
now:
"But, but, but, the problems in
NP-complete are too difficult to solve for
current computers because as the problem
size increases, the best known algorithms
have running time that grows as an
exponential in the size of the problem,
and exponential growth limits us to
problem instances of just small down to
tiny size."
Yup, can hear that complaint.
Good news, guys: The complaint is false
and does not correctly explain the
challenge of NP-complete.
E.g,, 0-1 integer linear programming is in
NP-complete, but I can write down, as fast
as I can type, such problems about as big
as you please that I, or anyone, can solve
quickly just by simple inspection.
It's true.
E.g., for any positive integer n, consider
the 0-1 integer linear programming problem
max z = 1 * x1 + 2 * x2 + ... + n * xn
subject to
x1 + x2 + ... + xn = 1
x1, x2, ..., xn = 0 or 1
So, the error in the complaint is that
actually the question of P versus NP has
to do with worst case instances of the
problems. But practical instances are not
all worst case, and for many of the
practical instances we can get solutions.
So, for any particular actual, specific,
instance of a real problem, bring it
forward -- you might be able to get a
solution.
And, wait, there's more!
For a problem like scheduling, mostly what
is desired is just to save money in the
actual operations, say, airlines where we
need to schedule the planes for the
planned flights, the crews, and
maintenance for the planes.
Since the planes do fly, tough to convince
me that the scheduling is impossible.
So, if spending $200 million a month on
operations, an optimal schedule could save
$20 million, can find a schedule that is
approximately optimal and saves all but
the last $100,000, then take the
$19,900,000 savings and be happy.
The claim "we want to show that P = NP so
that we can solve all these important
problems" has been going on since the
cartoon early in
Michael R. Garey and David S. Johnson,
'Computers and Intractability: A Guide to
the Theory of NP-Completeness'.
where the mathematician stood before the
business executive and admitted that he
could not solve the executive's problem
but neither could any of the
mathematicians in a long line.
Likely nonsense: The mathematician was
likely just looking for a long term job
and actually not at all interested in
solving the executive's problem.
Why? Because there was no indication that
the executive's problem was large and
worst case and needed an exactly optimal
solution instead of a nearly optimal
solution. The executive's problem might
have been relatively easy to solve, with a
nearly optimal solution and maybe with an
exactly optimal solution.
Indeed, the book was from Bell Labs where
one of their interests was network design.
Well, since the phones did work, somehow
Bell did find feasible solutions.
Optimal? Maybe not.
So, what was "the executive's problem"
that was in NP-complete and "too difficult
to solve?". Maybe he just wanted to
design a telecommunications network to
have the needed performance and
reliability and, otherwise, get the cost
down as much as possible or nearly so.
Finding an algorithm that shows that P =
NP is very likely a significantly
different problem, not his problem, and
not necessary for his problem.
This erroneous belief that all large
instances of problems in NP-complete are
too difficult to solve is too common:
E.g., once I got a problem in allocation
of marketing resources. The instance was
0-1 integer linear programming with 40,000
constraints and 600,000 variables.
I thought for a day or so, typed in some
software, did some Lagrangian
relaxation, and in 905 seconds on a 90
MHz PC got a feasible solution guaranteed
to be within 0.025% of optimality. Close
enough for gumment work!
Then, later, as I was considering network
design for the Internet, I got an
interview at a network design startup in
Texas and mentioned the problem with the
600,000 variables.
Well, the whole technical staff was on the
other side of the table, had heard the
horror stories about NP-complete in
college, and concluded to a person that I
was claiming to have done the impossible
and had to be lying.
I left without a job offer, and they soon
went out of business.
By the way, Mother Nature does protein
folding, right? Hmm ....
"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 that list were protein folding (to cure cancer) and scheduling."
Moreover, while the most obvious way of proving P = NP would be to find a P solution to an NP-complete problem, it's possible that someone will show existence of such a solution without being able to identify the particular solution. In that case, we don't get to do anything we couldn't do before.
It's also possible that we'll find a solution to an NP-complete problem that's O(n^million). That's in P, but may be substantially more out of reach than our O(2^n) approaches on realistically sized problems.
What is your point? That if we were all totally satisfied with half-ass solutions and non-answers, we wouldn't have to worry P = NP?
>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.
[+] [-] DanAndersen|11 years ago|reply
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 struggle with it. Does it simply come with practice or are there resources anyone here can recommend for improving one's ability to make hard ideas understandable?
[+] [-] nsnick|11 years ago|reply
He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest. https://www.ibm.com/developerworks/community/blogs/jfp/entry...
[+] [-] munchbunny|11 years ago|reply
1. Practice, practice, practice.
2. Find good examples (like this video) and try to extract and generalize the techniques that you think work really well.
and the last point which not everyone thinks of consciously:
3. Watch sports, read books, watch TV and movies, read the news, and go outside. When you must communicate by analogy, you need a broad pool of experiences to draw from so that you can match your audience.
[+] [-] minthd|11 years ago|reply
http://betterexplained.com/articles/adept-method/
It's by the author of better explained - a really great math teaching site.
[+] [-] yoha|11 years ago|reply
The video is very well structured and goes from very basic explanations of the concept of complexity up to the different classes of complexities.
[+] [-] mapmap|11 years ago|reply
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...
[+] [-] pjungwir|11 years ago|reply
After a bunch of Googling the only source I can find for this is a 2007 religious apologetics book with no Amazon reviews. I can't even find a French version of the quote. Anyone know if it's legitimate? And a more interesting question: if no one has ever even reviewed this book, how is it all over the Internet as the source of this quote?
EDIT: Oops, looks like it is not religious apologetics. Still, I'm curious how a (presumably manufactured) quote like this spreads from such an obscure source.
[+] [-] infogulch|11 years ago|reply
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!
[+] [-] eru|11 years ago|reply
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.)
[+] [-] swehner|11 years ago|reply
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-...
[+] [-] peeters|11 years ago|reply
[+] [-] Ocerge|11 years ago|reply
[+] [-] komodekork|11 years ago|reply
[+] [-] justifier|11 years ago|reply
[+] [-] z3t4|11 years ago|reply
I think that all problems with a set definition for "solved" is solvable as in "P".
For example, the rubik's cube is solved if all sides have a solid color. And is thus a "P".
[+] [-] Ar-Curunir|11 years ago|reply
P = Set of problems for which we can find a solution in polynomial time in the length of the input.
Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.
[+] [-] Gibbon1|11 years ago|reply
For a problem you can have a number of different algorithms to solve the problem. And a number of algorithms to check the solution to a problem. This is a point that is skipped over and trips lay people up because in school people are usually taught _the algorithm_ for solving a problem. But there are all sorts of ways to skin the cat mathematically. Some of these algorithms are great and some are 'bad'
Polynomial time algorithms are good. Ones that blow up exponentially are bad.
The question is, if you find a good polynomial time checking algorithm for a problem, does that mean there are polynomial time solving algorithms for that problem? Or not.
[+] [-] justifier|11 years ago|reply
each problem has a corresponding class(i) determined by a universal set of rules based on current solving algorithms and how they react to different input
in a beautiful and approachable paper by richard karp titled: reducibility among combinatorial problems(ii); karp showed that the hardest problems, that seem unable to be solved in polynomial or subpolynomial time, called NP-Hard, are basically all the same problem viewed from different perspectives
karp develops reducibility, a process used to show that one can reduce any of his 21 chosen problems into any of the others through a specific tree of transformations he calls reductions
this set of problems that form the tree of reductions is called NP-Complete
i say it is approachable because this paper develops reducibility and as such lacks any assumption about the reader's previous knowledge
.
* the algorithm:
check out this chart(iii) that lists some time complexities, you will see polynomial,P, time about mid way through
polynomial time is 2^O(log n) or poly(n), that 'O()' syntax is something called big O, which is analogous to a sort of algorithmic measurement unit(iv) derived from number of necessary operations in relation to the size of the input
all algorithms before the polynomial time listing are sub polynomial time for any inputs and as such are classified as P
.
* the size of the input:
lots of np problems have algorithm solutions that can solve specific inputs in polynomial time
sometimes those inputs are small, or follow a specific pattern, but a general purpose algorithm, or a collection of specific algorithms that can be proved to cover all possible inputs, that runs in a reduced(v) complexity of polynomial or sub polynomial time is necessary to be classified P
one way to prove P=NP is to take one of karp's problems and develop an algorithm that satisfies the above stated requirements
once developed karp's reductions can be used on the algorithm to show that all NP-Complete problems are in P as well, therefore P=NP
.
(i) http://en.wikipedia.org/wiki/Complexity_class
(ii) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
(iii) http://en.wikipedia.org/wiki/Time_complexity#Table_of_common...
(iv) http://en.wikipedia.org/wiki/Big_O_notation
(v) https://justin.abrah.ms/computer-science/big-o-notation-expl...
[+] [-] Zezima|11 years ago|reply
[+] [-] truncate|11 years ago|reply
http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321...
[+] [-] justifier|11 years ago|reply
and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii)
do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables
does your algorithm still work on these other inputs?
can you rewrite the algorithm to give the correct answers for these other inputs?
can you develop enough coverage to prove all possible inputs return correct values?
if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm?
for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii)
this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21
(i) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
(ii) http://mat.gsia.cmu.edu/orclass/integer/integer.html
(iii) http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00...
[+] [-] unknown|11 years ago|reply
[deleted]
[+] [-] MrBuddyCasino|11 years ago|reply
[+] [-] eru|11 years ago|reply
[+] [-] mottalrd|11 years ago|reply
[+] [-] enupten|11 years ago|reply
[+] [-] unknown|11 years ago|reply
[deleted]
[+] [-] omot|11 years ago|reply
[deleted]
[+] [-] graycat|11 years ago|reply
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 that list were protein folding (to cure cancer) and scheduling.
Right? Not so much:
If someone has an important problem in scheduling, protein folding or any of the NP-complete problems, bring forward that actual, specific, instance of the real problem.
Why? Because there's no proof and little evidence that finding a solution will be too difficult for "current computers".
To this claim I can hear the complaint now:
"But, but, but, the problems in NP-complete are too difficult to solve for current computers because as the problem size increases, the best known algorithms have running time that grows as an exponential in the size of the problem, and exponential growth limits us to problem instances of just small down to tiny size."
Yup, can hear that complaint.
Good news, guys: The complaint is false and does not correctly explain the challenge of NP-complete.
E.g,, 0-1 integer linear programming is in NP-complete, but I can write down, as fast as I can type, such problems about as big as you please that I, or anyone, can solve quickly just by simple inspection.
It's true.
E.g., for any positive integer n, consider the 0-1 integer linear programming problem
So, the error in the complaint is that actually the question of P versus NP has to do with worst case instances of the problems. But practical instances are not all worst case, and for many of the practical instances we can get solutions.So, for any particular actual, specific, instance of a real problem, bring it forward -- you might be able to get a solution.
And, wait, there's more!
For a problem like scheduling, mostly what is desired is just to save money in the actual operations, say, airlines where we need to schedule the planes for the planned flights, the crews, and maintenance for the planes.
Since the planes do fly, tough to convince me that the scheduling is impossible.
So, if spending $200 million a month on operations, an optimal schedule could save $20 million, can find a schedule that is approximately optimal and saves all but the last $100,000, then take the $19,900,000 savings and be happy.
The claim "we want to show that P = NP so that we can solve all these important problems" has been going on since the cartoon early in
Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness'.
where the mathematician stood before the business executive and admitted that he could not solve the executive's problem but neither could any of the mathematicians in a long line.
Likely nonsense: The mathematician was likely just looking for a long term job and actually not at all interested in solving the executive's problem.
Why? Because there was no indication that the executive's problem was large and worst case and needed an exactly optimal solution instead of a nearly optimal solution. The executive's problem might have been relatively easy to solve, with a nearly optimal solution and maybe with an exactly optimal solution.
Indeed, the book was from Bell Labs where one of their interests was network design. Well, since the phones did work, somehow Bell did find feasible solutions. Optimal? Maybe not.
So, what was "the executive's problem" that was in NP-complete and "too difficult to solve?". Maybe he just wanted to design a telecommunications network to have the needed performance and reliability and, otherwise, get the cost down as much as possible or nearly so. Finding an algorithm that shows that P = NP is very likely a significantly different problem, not his problem, and not necessary for his problem.
This erroneous belief that all large instances of problems in NP-complete are too difficult to solve is too common: E.g., once I got a problem in allocation of marketing resources. The instance was 0-1 integer linear programming with 40,000 constraints and 600,000 variables.
I thought for a day or so, typed in some software, did some Lagrangian relaxation, and in 905 seconds on a 90 MHz PC got a feasible solution guaranteed to be within 0.025% of optimality. Close enough for gumment work!
Then, later, as I was considering network design for the Internet, I got an interview at a network design startup in Texas and mentioned the problem with the 600,000 variables.
Well, the whole technical staff was on the other side of the table, had heard the horror stories about NP-complete in college, and concluded to a person that I was claiming to have done the impossible and had to be lying.
I left without a job offer, and they soon went out of business.
By the way, Mother Nature does protein folding, right? Hmm ....
[+] [-] dllthomas|11 years ago|reply
Moreover, while the most obvious way of proving P = NP would be to find a P solution to an NP-complete problem, it's possible that someone will show existence of such a solution without being able to identify the particular solution. In that case, we don't get to do anything we couldn't do before.
It's also possible that we'll find a solution to an NP-complete problem that's O(n^million). That's in P, but may be substantially more out of reach than our O(2^n) approaches on realistically sized problems.
[+] [-] Retra|11 years ago|reply
>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.
[+] [-] natehouk|11 years ago|reply
[+] [-] rrodriguez89|11 years ago|reply
[+] [-] Ar-Curunir|11 years ago|reply
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.