Is a proof of "P versus NP" itself subject to the P/NP argument?
September 1, 2017 5:30 AM Subscribe
There are reports again on the internet that "P versus NP" has been resolved. I'm not a mathematician, but did this set me wondering, as it is an interesting question, whether the proof of P/NP was in itself a case of a P/NP problem. So: Could we program a computer to attack P/NP?
For instance, as a thought experiment, would such a program be able to write programs that attack any problem to see if they are NP, for instance? Would it be able to write itself (as an example of such a program)? Apologies for the vagueness here, IANAM, and am equally interested in the philosophical implications, and am very happy to be corrected on any of these ramblings.
For instance, as a thought experiment, would such a program be able to write programs that attack any problem to see if they are NP, for instance? Would it be able to write itself (as an example of such a program)? Apologies for the vagueness here, IANAM, and am equally interested in the philosophical implications, and am very happy to be corrected on any of these ramblings.
Professor Blum has acknowledged his approach is mistaken. So no proof. But I think you have some essential insight that the statement of the problem may be an example of the problem. Which is rather meta and circular but mathematicians can certainly handle self referential problems.
Discussion in /r/math suggest that the proof will come (if it ever does) from an unexpected direction. It seems a lot of obvious and obscure proofs have been tried. So while there are automated proof systems and some proofs like the four color map theorem used computers, just throwing big fast cpu's at this kind may be a tool to find an insight or check a lot of examples it seems unlikely to "solve" the problem. So, ah, no and yes to your core question.
posted by sammyo at 5:50 AM on September 1, 2017
Discussion in /r/math suggest that the proof will come (if it ever does) from an unexpected direction. It seems a lot of obvious and obscure proofs have been tried. So while there are automated proof systems and some proofs like the four color map theorem used computers, just throwing big fast cpu's at this kind may be a tool to find an insight or check a lot of examples it seems unlikely to "solve" the problem. So, ah, no and yes to your core question.
posted by sammyo at 5:50 AM on September 1, 2017
On your follow up, yeah it's really hard to wrap one's head around. But it's not about "not-programmable" but more is it practical to program. It's also confusing as many examples are seemingly solved problems (organizing teams) which for a small subset are "solved" by regular folks all the time. But the mathy problem is looking at bigger numbers, so finding the best arrangement of 10 teams may be annoying -- finding the solution to n teams where n is a ridiculous big number is essentially impossible as the steps to find a solution for n may be n factorial.
The question does n = np is more convoluted as it's not exactly solving the problem but more can we even decide if we can solve a specific problem.
I think. I hope I have not wandered off on a mistaken tangent. ;-)
posted by sammyo at 6:05 AM on September 1, 2017
The question does n = np is more convoluted as it's not exactly solving the problem but more can we even decide if we can solve a specific problem.
I think. I hope I have not wandered off on a mistaken tangent. ;-)
posted by sammyo at 6:05 AM on September 1, 2017
Best answer: > Is it even useful for me to equate (in my mind) NP with 'non-programmable' ...?
That's not a good intuition to have, because there are programs solving all problems in NP (but some of them might need exponential time) and some problems in NP do have programs solving them in polynomial time.
If you're a beginner, it's a good idea to stick close to the definitions until you are confident working with them. So, you'll probably recall that the class NP:
1. is a class of yes/no problems
2. that can be solved by a nondeterministic program
3. in polynomial time.
This can be a bit tricky to get your head around because the terms are used in specialized senses:
1. A yes/no problem (or decision problem) is an infinite set of yes/no questions.
2. A yes/no problem is solved by a nondeterministic program if there's a program P such that, for every question in the problem whose answer is "yes", there exists a "certificate" C such that when P is run on the input C, it outputs "yes", and for every question in the problem whose answer is "no", there is no such certificate. ⟵ This definition is far from intuitive and will take some practice before you get it!
3. A program runs in polynomial time if there are numbers k and p and m0 such that whenever you start the program on an input of length m > m0, the time taken by the program is no more than kmp (where time is measured in units like number of instructions executed — the exact details will depend on how we specify our programs).
For example:
1. Take the set of questions {"is 1 composite?" "is 2 composite?", ..., "is 15,485,869 composite?", ...}.
2. For the question "is n composite?" we can take the "certificate" to be an integer x. The program P outputs "yes" if x is greater than 1 and the remainder is zero when n is divided by x; and outputs "no" otherwise.
3. The program P has to compute a remainder and compare it with zero. With the schoolbook long division algorithm this takes time proportional to the square of the number of digits in n, so we can take p=2 and m0=0 and k to be whatever constant of proportionality comes out of our implementation of the long division algorithm.
This shows that the problem "is n composite?" is in the class NP.
posted by cyanistes at 6:48 AM on September 1, 2017 [7 favorites]
That's not a good intuition to have, because there are programs solving all problems in NP (but some of them might need exponential time) and some problems in NP do have programs solving them in polynomial time.
If you're a beginner, it's a good idea to stick close to the definitions until you are confident working with them. So, you'll probably recall that the class NP:
1. is a class of yes/no problems
2. that can be solved by a nondeterministic program
3. in polynomial time.
This can be a bit tricky to get your head around because the terms are used in specialized senses:
1. A yes/no problem (or decision problem) is an infinite set of yes/no questions.
2. A yes/no problem is solved by a nondeterministic program if there's a program P such that, for every question in the problem whose answer is "yes", there exists a "certificate" C such that when P is run on the input C, it outputs "yes", and for every question in the problem whose answer is "no", there is no such certificate. ⟵ This definition is far from intuitive and will take some practice before you get it!
3. A program runs in polynomial time if there are numbers k and p and m0 such that whenever you start the program on an input of length m > m0, the time taken by the program is no more than kmp (where time is measured in units like number of instructions executed — the exact details will depend on how we specify our programs).
For example:
1. Take the set of questions {"is 1 composite?" "is 2 composite?", ..., "is 15,485,869 composite?", ...}.
2. For the question "is n composite?" we can take the "certificate" to be an integer x. The program P outputs "yes" if x is greater than 1 and the remainder is zero when n is divided by x; and outputs "no" otherwise.
3. The program P has to compute a remainder and compare it with zero. With the schoolbook long division algorithm this takes time proportional to the square of the number of digits in n, so we can take p=2 and m0=0 and k to be whatever constant of proportionality comes out of our implementation of the long division algorithm.
This shows that the problem "is n composite?" is in the class NP.
posted by cyanistes at 6:48 AM on September 1, 2017 [7 favorites]
Is it even useful for me to equate (in my mind) NP with 'non-programmable' ...?
No, for any NP-complete problem there's a straightforward (but silly) exponential time algorithm in the worst case, so NP complete problems are all 'programmable', just not necessarily tractable. It may be useful to look at the exponential time hypothesis to try to get a handle on this fact.
Given your question I think a next step would be to try to understand what it means to be NP complete, probably by looking at a proof that reduces some problem to a known NP complete problem. That would give you a much better sense of what proofs in this area look like and help refine (or just change) your main question. There's lots of resources out there for this if you google around (including the original reduction of 3-SAT to SAT), though they usually are on the technical side, so I'm not sure what to suggest beyond the obvious textbook options that I learned from. You could also have a look at whatever open course stuff there is out there, for example [I haven't watched this]. But maybe someone will have better suggestions for more introductory versions of these proofs.
posted by advil at 7:41 AM on September 1, 2017 [1 favorite]
No, for any NP-complete problem there's a straightforward (but silly) exponential time algorithm in the worst case, so NP complete problems are all 'programmable', just not necessarily tractable. It may be useful to look at the exponential time hypothesis to try to get a handle on this fact.
Given your question I think a next step would be to try to understand what it means to be NP complete, probably by looking at a proof that reduces some problem to a known NP complete problem. That would give you a much better sense of what proofs in this area look like and help refine (or just change) your main question. There's lots of resources out there for this if you google around (including the original reduction of 3-SAT to SAT), though they usually are on the technical side, so I'm not sure what to suggest beyond the obvious textbook options that I learned from. You could also have a look at whatever open course stuff there is out there, for example [I haven't watched this]. But maybe someone will have better suggestions for more introductory versions of these proofs.
posted by advil at 7:41 AM on September 1, 2017 [1 favorite]
Best answer: so, a key idea: P is contained in NP. if you imagine a venn diagram, picture P as a small circle inside NP. that's what we believe but can't prove. it's possible and unlikely that P and NP are just the same circle.
intuitively it's not bad to think of P as "something that has a program that runs reasonably fast".
there are lots of equivalent definitions of NP but one of them is that there's a "certificate" that can be checked in polynomial time. in layman's terms, if you come up with a candidate answer, i can easily check if it's valid or not, but actually finding the right answer might be very difficult. things could be worse! there are classes we believe harder than NP, where even checking if you got the right answer is hopeless.
mathematical theorem-proving falls into NP in some sense. if i come up with a (very thorough, machine-readable) proof of a theorem, it's possible to mechanically and easily check if it's valid. we have technology for doing this right now. intuitively, imagine going line-by-line through somebody's algebra homework and just checking that each step is valid, vs. the challenge of actually solving the problem.
now, you can come up with proofs, but it's tricky. the easiest way is just to write down every possible proof, but that would take squintillions of years before you got anything useful probably, but it's technically a correct approach. there might be cleverer solutions. what we believe but can't prove about NP is that it's different than P, that is, maybe there are cleverer solutions that only take a bajillion years, which is less than squintillions, but we're never going to get something fast enough.
P not equal to NP is just another statement that has a proof, so in theory we could just search for it just like any other mathematical theorem. so your intuition is correct. but the entire universe would die a heat death before we found the proof, probably.
in the unlikely event that P did equal NP, and we had a constructive proof of this (meaning an actually usable program) then I guess all the mathematicians would be out of a job, because we could easily and mechanically prove any theorem we cared about. but that's likely false.
there is a notion of things that are "non-programmable" (or the usual word used is "computable") you should read about the Halting Problem if you think that's a neat idea. It's what Alan Turing originally worked on and predates computational complexity theory. Everything in P and NP is computable -- so there's always a valid program, it just might take a really long time.
posted by vogon_poet at 9:37 AM on September 1, 2017 [2 favorites]
intuitively it's not bad to think of P as "something that has a program that runs reasonably fast".
there are lots of equivalent definitions of NP but one of them is that there's a "certificate" that can be checked in polynomial time. in layman's terms, if you come up with a candidate answer, i can easily check if it's valid or not, but actually finding the right answer might be very difficult. things could be worse! there are classes we believe harder than NP, where even checking if you got the right answer is hopeless.
mathematical theorem-proving falls into NP in some sense. if i come up with a (very thorough, machine-readable) proof of a theorem, it's possible to mechanically and easily check if it's valid. we have technology for doing this right now. intuitively, imagine going line-by-line through somebody's algebra homework and just checking that each step is valid, vs. the challenge of actually solving the problem.
now, you can come up with proofs, but it's tricky. the easiest way is just to write down every possible proof, but that would take squintillions of years before you got anything useful probably, but it's technically a correct approach. there might be cleverer solutions. what we believe but can't prove about NP is that it's different than P, that is, maybe there are cleverer solutions that only take a bajillion years, which is less than squintillions, but we're never going to get something fast enough.
P not equal to NP is just another statement that has a proof, so in theory we could just search for it just like any other mathematical theorem. so your intuition is correct. but the entire universe would die a heat death before we found the proof, probably.
in the unlikely event that P did equal NP, and we had a constructive proof of this (meaning an actually usable program) then I guess all the mathematicians would be out of a job, because we could easily and mechanically prove any theorem we cared about. but that's likely false.
there is a notion of things that are "non-programmable" (or the usual word used is "computable") you should read about the Halting Problem if you think that's a neat idea. It's what Alan Turing originally worked on and predates computational complexity theory. Everything in P and NP is computable -- so there's always a valid program, it just might take a really long time.
posted by vogon_poet at 9:37 AM on September 1, 2017 [2 favorites]
oh: the standard introductory textbook on this stuff is Michael Sipser's book. it's very expensive but so good as to be worth the money, although you could certainly pirate it as well.
the standard graduate texts are by Papadimitriou and another one by Arora and Barak. You don't want to mess with these, they're extremely terse and technical.
the best book I could recommend, though is "The Nature of Computation" by Moore and Mertens. It's a thorough book, not a popularization, but extremely well-written and fun and insightful and if you don't feel like really digging into the technical stuff, you could just let your eyes glaze over for those parts. it gets rave reviews from everyone, for good reason.
strongly endorse taking a look at that book.
posted by vogon_poet at 10:01 AM on September 1, 2017
the standard graduate texts are by Papadimitriou and another one by Arora and Barak. You don't want to mess with these, they're extremely terse and technical.
the best book I could recommend, though is "The Nature of Computation" by Moore and Mertens. It's a thorough book, not a popularization, but extremely well-written and fun and insightful and if you don't feel like really digging into the technical stuff, you could just let your eyes glaze over for those parts. it gets rave reviews from everyone, for good reason.
strongly endorse taking a look at that book.
posted by vogon_poet at 10:01 AM on September 1, 2017
here's a rave review of The Nature of Computation that also has some good insight into the difference between problems in P and in NP.
posted by vogon_poet at 10:07 AM on September 1, 2017
posted by vogon_poet at 10:07 AM on September 1, 2017
Careful, vogon_poet. Determining whether a statement is provable (i.e. the Entscheidungsprobem) is undecidable, so in that sense mathematicians are safe from being put out of work by computers, even if P = NP.
posted by eruonna at 10:50 AM on September 1, 2017 [2 favorites]
posted by eruonna at 10:50 AM on September 1, 2017 [2 favorites]
that's why i weaseled out of it with "in some sense"!
i don't understand the arguments but people have suggested it would be very surprising if P ?= NP were undecidable in the usual systems.
posted by vogon_poet at 11:04 AM on September 1, 2017
i don't understand the arguments but people have suggested it would be very surprising if P ?= NP were undecidable in the usual systems.
posted by vogon_poet at 11:04 AM on September 1, 2017
Response by poster: Everyone! - many thanks for all your comments and suggestions - as always, very useful - and apologies for the delayed feedback. This is a fascinating topic for me, albeit one I'm still wrapping my head around.
posted by carter at 5:09 AM on October 7, 2017 [1 favorite]
posted by carter at 5:09 AM on October 7, 2017 [1 favorite]
This thread is closed to new comments.
posted by carter at 5:42 AM on September 1, 2017