Consequences to P=NP
Moderators: phlip, Moderators General, Prelates
 Mach1ne
 Posts: 35
 Joined: Tue Feb 24, 2009 5:20 pm UTC
 Location: This exact location but 3 minutes from now
Consequences to P=NP
This may not go in this section of the forums (apologies if it doesn't), but I was curious as to what one could expect to happen if someone proved P=NP.
I know that supposedly eCommerce protection sometimes depends on P != NP, and I have heard that if it was shown that P=NP then you could see a collapse in eCommerce. Also if this was shown then you could have computers spitting out proofs to mathematical problems that were of reasonable length. Does this mean a collapse of mathematics in some ways?
What other consequences would there be(positive or negative)?
I know that supposedly eCommerce protection sometimes depends on P != NP, and I have heard that if it was shown that P=NP then you could see a collapse in eCommerce. Also if this was shown then you could have computers spitting out proofs to mathematical problems that were of reasonable length. Does this mean a collapse of mathematics in some ways?
What other consequences would there be(positive or negative)?
Re: Consequences to P=NP
Generally speaking, the reason ecommerce would collapse is that cryptography would collapse. No one's going to buy anything over the internet if their creditcard information isn't safe. Now, why would cryptography collapse?
Most modern cryptography, as far as I understand, depends on factoring products of really huge primes. This takes advantage of the fact that it's really easy to multiply two numbers together and find their product, but it's not easy to find the two unique numbers that you have to multiply if all you have is their product. P and NP come in because they're technical ways of talking about "easy" and "not easy." A problem is in P is there is a deterministic algorithm that always solves it in polynomial time. It's in NP if there's a nondeterministic algorithm that always solves it in polynomial time. (NP stands for nondeterministic polynomial time.)
So what if P == NP? That means that problems that we know are NP (like factoring the product of two huge primes) are also in P. This means that somewhere, there must exist some algorithm that will solve our primes problem, and hence break crypto, in a way that's "easy" for a computer to calculate. That spells trouble.
Now P is provably different from EXPTIME (which is the class of problems that can be solved deterministically in exponential time). So maybe if we all switched to cryptography that depends on EXPTIME problems, we'd be safe. But that'll be really inefficient: the whole point of cryptography is that it's really fast for someone who knows the secret, but horrendously slow for someone who doesn't.
In conclusion, if "fast" and "slow" mean the same thing, then the asymmetries in modern cryptography schemes aren't really asymmetries at all. (I've had one semester of theory of computation; if someone with a better crypto background wants to chime in here, please do.)
Also, we should note that proving P == NP does not, in itself, cause cryptography to collapse. But it does prove the existence of a P algorithm for factoring, and once people know it exists, we'll obviously have a lot of people trying to find it. One they find it, though  that's when current crypto is finished. As it is, most people think such an algorithm does not exist (because they think P and NP are different).
Most modern cryptography, as far as I understand, depends on factoring products of really huge primes. This takes advantage of the fact that it's really easy to multiply two numbers together and find their product, but it's not easy to find the two unique numbers that you have to multiply if all you have is their product. P and NP come in because they're technical ways of talking about "easy" and "not easy." A problem is in P is there is a deterministic algorithm that always solves it in polynomial time. It's in NP if there's a nondeterministic algorithm that always solves it in polynomial time. (NP stands for nondeterministic polynomial time.)
So what if P == NP? That means that problems that we know are NP (like factoring the product of two huge primes) are also in P. This means that somewhere, there must exist some algorithm that will solve our primes problem, and hence break crypto, in a way that's "easy" for a computer to calculate. That spells trouble.
Now P is provably different from EXPTIME (which is the class of problems that can be solved deterministically in exponential time). So maybe if we all switched to cryptography that depends on EXPTIME problems, we'd be safe. But that'll be really inefficient: the whole point of cryptography is that it's really fast for someone who knows the secret, but horrendously slow for someone who doesn't.
In conclusion, if "fast" and "slow" mean the same thing, then the asymmetries in modern cryptography schemes aren't really asymmetries at all. (I've had one semester of theory of computation; if someone with a better crypto background wants to chime in here, please do.)
Also, we should note that proving P == NP does not, in itself, cause cryptography to collapse. But it does prove the existence of a P algorithm for factoring, and once people know it exists, we'll obviously have a lot of people trying to find it. One they find it, though  that's when current crypto is finished. As it is, most people think such an algorithm does not exist (because they think P and NP are different).
Sandry wrote:Bless you, Briareos.
Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.
Re: Consequences to P=NP
First of all, the people who came up with the key insights in determining this result would become insanely famous.
Secondly, if the polynomial time algorithm that can solve all these problems has low enough degree, then computers will become a whole lot faster, and a lot of important problems will have solutions.
I'm pretty sure that having efficient algorithms for all these problems would lead pretty quickly to strong AI.
In terms of mathematical collapse, the petting zoo will certainly collapse a great deal.
Note to the previous poster: While factoring is in NP, it is not proven NPcomplete. In other words, a polynomial time algorithm may exist for factoring even if P!=NP. And RSA is under attack even if factoring is NPcomplete, because quantum computers, once they are scalable and feasible, can find a factor with polynomially high probability, since there is a polynomialsize quantum circuit for fourier transforms. (See Shor's Algorithm) Fortunately, quantum computers also provide us the ability to do unbreakable crypto, so it's not too huge a loss in the long run.
Secondly, if the polynomial time algorithm that can solve all these problems has low enough degree, then computers will become a whole lot faster, and a lot of important problems will have solutions.
I'm pretty sure that having efficient algorithms for all these problems would lead pretty quickly to strong AI.
In terms of mathematical collapse, the petting zoo will certainly collapse a great deal.
Note to the previous poster: While factoring is in NP, it is not proven NPcomplete. In other words, a polynomial time algorithm may exist for factoring even if P!=NP. And RSA is under attack even if factoring is NPcomplete, because quantum computers, once they are scalable and feasible, can find a factor with polynomially high probability, since there is a polynomialsize quantum circuit for fourier transforms. (See Shor's Algorithm) Fortunately, quantum computers also provide us the ability to do unbreakable crypto, so it's not too huge a loss in the long run.
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Consequences to P=NP
It's not exactly quantum computers, but quantum mechanics that gives us unbreakable encryption, and there are encryption schemes that are "quantum proof" already but don't require a quantum computer to be efficient for the keyholders.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
Re: Consequences to P=NP
Berengal wrote:It's not exactly quantum computers, but quantum mechanics that gives us unbreakable encryption, and there are encryption schemes that are "quantum proof" already but don't require a quantum computer to be efficient for the keyholders.
You are correct, of course. What I meant to say was "the integration of quantumcoherent devices with computers"
Re: Consequences to P=NP
quintopia wrote:I'm pretty sure that having efficient algorithms for all these problems would lead pretty quickly to strong AI.
I don't know about that. First of all, 'strong AI' is not an easy problem to define formally. Even if all the problems on that list magically became tractable tomorrow, we wouldn't know where to begin the design of a strong AI.
Second, a lot of the relevant problems already have approximate algorithms that give pretty good answers. Being able to solve the problems exactly would improve solution quality, but (in most cases) wouldn't enable us to do things we currently can't do at all.
Third, a lot of relevant problems would continue to be intractable even if P=NP. For instance, a lot of interesting AI problems are #Pcomplete. (However, if P=NP, we'd be able to get arbitrarily good approximations in polynomial time; right now, we just take the best solution we can get in the available time. It isn't clear how much practical difference this would make.)
Re: Consequences to P=NP
I don't know if there really would be any difference. There may be a way to solve 3SAT given, say, a 200dimension dynamic programming table, or by an algorithm that runs in n^100 time. Still "polynomial," but that's sort of irrelevant. Even if P==NP, it is highly unlikely that we could find a tractable algorithm for an NPcomplete problem, so we still would be using approximation algorithms that run in a reasonable amount of time
Re: Consequences to P=NP
Nath wrote:Second, a lot of the relevant problems already have approximate algorithms that give pretty good answers. Being able to solve the problems exactly would improve solution quality, but (in most cases) wouldn't enable us to do things we currently can't do at all.
For many problems, we still only have constant factor approximations. The set of problems for which a PTAS exists is actually quite small.
Nath wrote:Third, a lot of relevant problems would continue to be intractable even if P=NP.
True. P=#P would be much more interesting.
(And incredibly unlikely.)
Re: Consequences to P=NP
quintopia wrote:For many problems, we still only have constant factor approximations.
Yes, or not even that. Some interesting problems have approximation algorithms with no real guarantees at all, but that still tend to work in practice. It's horribly inelegant, but the fact remains that we can often come up with useful solutions to NPhard problems. Having efficient exact algorithms would improve only solution quality in these situations. (Then again, for some problems you want an exact solution or none at all. While we have practically useful but guaranteeless algorithms for these problems, they don't always find a solution.)
Re: Consequences to P=NP
Briareos wrote:Generally speaking, the reason ecommerce would collapse is that cryptography would collapse. No one's going to buy anything over the internet if their creditcard information isn't safe. Now, why would cryptography collapse?
Most modern cryptography, as far as I understand, depends on factoring products of really huge primes. This takes advantage of the fact that it's really easy to multiply two numbers together and find their product, but it's not easy to find the two unique numbers that you have to multiply if all you have is their product. P and NP come in because they're technical ways of talking about "easy" and "not easy." A problem is in P is there is a deterministic algorithm that always solves it in polynomial time. It's in NP if there's a nondeterministic algorithm that always solves it in polynomial time. (NP stands for nondeterministic polynomial time.)
So what if P == NP? That means that problems that we know are NP (like factoring the product of two huge primes) are also in P. This means that somewhere, there must exist some algorithm that will solve our primes problem, and hence break crypto, in a way that's "easy" for a computer to calculate. That spells trouble.
Now P is provably different from EXPTIME (which is the class of problems that can be solved deterministically in exponential time). So maybe if we all switched to cryptography that depends on EXPTIME problems, we'd be safe. But that'll be really inefficient: the whole point of cryptography is that it's really fast for someone who knows the secret, but horrendously slow for someone who doesn't.
In conclusion, if "fast" and "slow" mean the same thing, then the asymmetries in modern cryptography schemes aren't really asymmetries at all. (I've had one semester of theory of computation; if someone with a better crypto background wants to chime in here, please do.)
Also, we should note that proving P == NP does not, in itself, cause cryptography to collapse. But it does prove the existence of a P algorithm for factoring, and once people know it exists, we'll obviously have a lot of people trying to find it. One they find it, though  that's when current crypto is finished. As it is, most people think such an algorithm does not exist (because they think P and NP are different).
You can still do cryptography if P=NP, you just don't get as large of an advantage over the attacker anymore. The biggest difference normal people would notice is transactions taking longer, and maybe the expiry dates on credit cards decreasing.
Don't pay attention to this signature, it's contradictory.
 You, sir, name?
 Posts: 6983
 Joined: Sun Apr 22, 2007 10:07 am UTC
 Location: Chako Paul City
 Contact:
Re: Consequences to P=NP
The mathematics of nonpolynomial solutions have bothered me for a while. (I'm a physicist, so don't shoot me over my crimes against CS), but wouldn't it just be possible to Taylor expand whatever nonpolynomial time you have into a polynomial? Even exponential time is, strictly speaking polynomial time... Furthermore, at any local region of time, there are always polynomial complexities that are (locally) indistinguishable from some given nonpolynomial ones.
The only complexities that would resist this method would be bizarre and full of discontinuities, which is certainly rare enough to be a special case.
The only complexities that would resist this method would be bizarre and full of discontinuities, which is certainly rare enough to be a special case.
Spoiler:
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

 Posts: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
Re: Consequences to P=NP
The error of a polynomial approximation is only bounded on a bounded interval. Complexity is concerned with asymptotics.
GENERATION 16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Consequences to P=NP
NP isn't nonpolynomial, but nondeterministicpolynomial, which means a nondeterministic turing machine could do the algorithm in polynomial time. For example, a nondeterministic turing machine could search a perfectly balanced binary tree in O(log n) time, but a deterministic machine needs O(n) time (assuming backtracking is free).
There exists two values k and c such that k2^n + c grows faster than n^p for any p, doesn't it? Polynomials are, as we all know, on the form n^a + n^b + n^c etc. If a > b then n^a grows faster than n^b at infinity, so we can discard all but the highestranking polynomial. This means all polynomials can be written a O(n^k) in big oh notation. Since the fastestgrowing polynomial is a polynomial, and O(2^n) can always outgrow any polynomial, it can't itself be a polynomial, can it?
Mixing symbol names and sketchy math for the win!
There exists two values k and c such that k2^n + c grows faster than n^p for any p, doesn't it? Polynomials are, as we all know, on the form n^a + n^b + n^c etc. If a > b then n^a grows faster than n^b at infinity, so we can discard all but the highestranking polynomial. This means all polynomials can be written a O(n^k) in big oh notation. Since the fastestgrowing polynomial is a polynomial, and O(2^n) can always outgrow any polynomial, it can't itself be a polynomial, can it?
Mixing symbol names and sketchy math for the win!
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
Re: Consequences to P=NP
This isn't quite what you've asked, but having spoken to most of the professors in my university's applied math department about this; most of them think that in the next two decades or so someone will prove P != NP and several are betting that it will be Timothy Chan (University of Waterloo, look him up, he's brilliant).

 Posts: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
Re: Consequences to P=NP
Meteorswarm wrote:As a similar question, what would happen if it were proved that P=NP was unprovable given the standard set of axioms and rules of inference, or maybe an even broader range?
For most practical purposes, this would have the same consequences as someone proving that P != NP.
Incidentally, if anyone actually wants to bet, I'll happily wager that Timothy Chan does not prove P == NP in the next two decades.
GENERATION 16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
Re: Consequences to P=NP
Nath wrote:Second, a lot of the relevant problems already have approximate algorithms that give pretty good answers. Being able to solve the problems exactly would improve solution quality, but (in most cases) wouldn't enable us to do things we currently can't do at all.
Searching for a strategy/program to solve a problem+a limited length proof it is correct given certain assumptions with an approximate algorithm would probably give proofs relying on a miracle happening somewhere in the middle.
Training neural networks with backpropagation is usually only done with a small number of layers because it easily gets stuck in local minima.
Exact solutions of large constraint problems should be able to make mincemeat of both.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Consequences to P=NP
stephentyrone wrote:For most practical purposes, this would have the same consequences as someone proving that P != NP.
Incidentally, if anyone actually wants to bet, I'll happily wager that Timothy Chan does not prove P == NP in the next two decades.
That's cheating. Proving P == NP would be so awesome I'd happily hand over a decent bundle of cash in exchange for seeing that proof.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 111
 Joined: Tue Feb 24, 2009 7:51 pm UTC
Re: Consequences to P=NP
What if someone proved that P==NP is unprovable and proved P!=NP is unprovable?
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Consequences to P=NP
So, that would mean that any algorithm that does do an NP task in P time cannot be proven to do the task in P time (given framework F)?
Ie, it just demonstrates that our logical framework surrounding computers is lacking. This might be insurmountable (in a Godel sense).
Then again, maybe we could find an algorithm that, if there is an algorithm that does an NP problem in P time, it terminates. And otherwise, it does not terminate. If such an algorithm exists, then you could generate a metaproof (outside the framework F) that shows that P!=NP.
Remember that "cannot be proven" needs to be phrased as "cannot be proven in framework F" (as you can prove P=NP in some framework  simply take our standard framework, add P=NP as an axiom, and done. You do not, however, know if that new framework is consistent).
Ie, it just demonstrates that our logical framework surrounding computers is lacking. This might be insurmountable (in a Godel sense).
Then again, maybe we could find an algorithm that, if there is an algorithm that does an NP problem in P time, it terminates. And otherwise, it does not terminate. If such an algorithm exists, then you could generate a metaproof (outside the framework F) that shows that P!=NP.
Remember that "cannot be proven" needs to be phrased as "cannot be proven in framework F" (as you can prove P=NP in some framework  simply take our standard framework, add P=NP as an axiom, and done. You do not, however, know if that new framework is consistent).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Consequences to P=NP
Only interesting inasmuch as it'd mean there was no sound and complete axiomatisation... by definition, any complete axiom set will have an answer one way or the other about P=NP.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Consequences to P=NP
phlip wrote:Only interesting inasmuch as it'd mean there was no sound and complete axiomatisation... by definition, any complete axiom set will have an answer one way or the other about P=NP.
Don't we already know there is no sound and complete axiomatisation (firefox spellcheck fail!) powerful enough to express (1+1 = 2, etc), let alone for a Turing Machine. This is a nearly 80 year old result.
Ok, you can get sound and completeness by throwing away effectiveness. Ie, throw away the ability to check proofs for correctness. Logic without effectiveness is not really logic (despite what secondorder logicians would claim  after all, how can you trust the claim of a second order logician?)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Consequences to P=NP
andy33gmail wrote:What if someone proved that P==NP is unprovable and proved P!=NP is unprovable?
It would mean there might be NP solving algorithms in P, but none of them were provably in P. I think that's really unlikely.
I think the really interesting part is that there are oracles relative to which P=NP and oracles relative to which P!=NP. (If we add different 'magical' computational abilities to computers, the answer can change).
Don't pay attention to this signature, it's contradictory.

 Posts: 111
 Joined: Tue Feb 24, 2009 7:51 pm UTC
Re: Consequences to P=NP
It would mean there might be NP solving algorithms in P, but none of them were provably in P. I think that's really unlikely.
Couldn't it also mean there are algorithms in P which appear to solve all NP complete problems but cannot be proven to do so? For example, if they solve every example of a 3SAT problem we throw at them but we can't prove they'll always work.
Re: Consequences to P=NP
andy33gmail wrote:It would mean there might be NP solving algorithms in P, but none of them were provably in P. I think that's really unlikely.
Couldn't it also mean there are algorithms in P which appear to solve all NP complete problems but cannot be proven to do so? For example, if they solve every example of a 3SAT problem we throw at them but we can't prove they'll always work.
Give me am algorithm in P that can't be proven to work and I can produce an algorithm which definitely works but can't be proven to be in P. Just run a brute force search alongside your normal algorithm.
So, you're right that it could meant that, but you're wrong that my original sentence was incomplete in that way.
Don't pay attention to this signature, it's contradictory.
Re: Consequences to P=NP
I can't believe I forgot about this.
There is no way we could prove P=NP and not have an algorithm we knew was in P, because we already know an algorithm that is in P if and only if P=NP ( http://en.wikipedia.org/wiki/P%3Dnp#Pol ... algorithms ).
There is no way we could prove P=NP and not have an algorithm we knew was in P, because we already know an algorithm that is in P if and only if P=NP ( http://en.wikipedia.org/wiki/P%3Dnp#Pol ... algorithms ).
Code: Select all
FOR N = 1...infinity
FOR P = 1...N
Run program number P for N steps with input S
IF the program outputs a list of distinct integers
AND the integers are all in S
AND the integers sum to 0
THEN
OUTPUT "yes" and HALT
Don't pay attention to this signature, it's contradictory.

 Posts: 32
 Joined: Wed May 27, 2009 2:32 am UTC
Re: Consequences to P=NP
I haven't had a formal theory course yet, but this is something that I have wondered about for a while now, and relates to this topic eventually. Given a finite set of axioms, is there any any idea regarding the time complexity of deriving proving or disproving statement that is derivable from the axioms? (Clearly the general case of "any statement in the axiomatic system" is uncomputable for an axiomatic system strong enough to represent the natural numbers, at least as far as I understand Godel's Incompleteness Theorem).
I was wondering what sort of effect P=NP would have on automated theorem proving.
I was wondering what sort of effect P=NP would have on automated theorem proving.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Consequences to P=NP
Checking a proof of length n for theorem T is in P.
Thus "is there a proof of theorem T of length n or less" is in NP.
Thus "is there a proof of theorem T of length n or less" is in NP.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 213
 Joined: Wed Sep 10, 2008 3:54 am UTC
Re: Consequences to P=NP
andy33gmail wrote:What if someone proved that P==NP is unprovable and proved P!=NP is unprovable?
Doesn't one imply the next? P==NP  P!=NP. If I can't prove P==NP, and can prove that I cannot, I have also proved there is no proof to P!=NP. Any proof of P!=NP violates the proof of not proving P==NP. Any proof of P!=NP or even proof of it's provability would have to be eliminated in order to prove that there is no proof of P==NP.
This post is fiftyproof.
Edit: oh, I see. That makes perfect sense.
Last edited by Agent_Irons on Wed Jun 17, 2009 3:23 am UTC, edited 1 time in total.
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Consequences to P=NP
I think andy was using "unprovable" to mean "You can't prove X is true", as opposed to "You can't prove X is either true or false"... which would make it not redundant.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Consequences to P=NP
is 1 a whole number?
P=NP
P=5 (or any other whole number)
N=1
5=(1)(5)
P=NP
P=5 (or any other whole number)
N=1
5=(1)(5)
Re: Consequences to P=NP
zalzane wrote:is 1 a whole number?
P=NP
P=5 (or any other whole number)
N=1
5=(1)(5)
If that's a joke, it's correct but not particularly funny.
If that's not a joke, it's hilarious but not correct.
You see the bind I'm in? I don't know what to critique and what to praise.
Don't pay attention to this signature, it's contradictory.
Re: Consequences to P=NP
Strilanc wrote:zalzane wrote:is 1 a whole number?
P=NP
P=5 (or any other whole number)
N=1
5=(1)(5)
If that's a joke, it's correct but not particularly funny.
If that's not a joke, it's hilarious but not correct.
You see the bind I'm in? I don't know what to critique and what to praise.
Well nobody said N couldn't equal 1.

 Posts: 111
 Joined: Tue Feb 24, 2009 7:51 pm UTC
Re: Consequences to P=NP
Giving you the benefit of the doubt and assuming you're not understanding the question.
We're referring to NP completeness, as explain on your favourite encyclopaedia or semidecent 2nd year Computer Science course
http://en.wikipedia.org/wiki/NP_completeness
We're referring to NP completeness, as explain on your favourite encyclopaedia or semidecent 2nd year Computer Science course
http://en.wikipedia.org/wiki/NP_completeness
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Consequences to P=NP
In the question of "is the zalzane poster making a joke, or not understanding it", I believe that this problem is in NP, as there is a string polynomial in the length of the question that can determine if the person is making a joke.
... or is it too soon to crack a joke about zalzane's bad joke?
... or is it too soon to crack a joke about zalzane's bad joke?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Consequences to P=NP
freaking CS nerds are making fun of me!
Keep in mind this is the same zalzane who is in 11th grade and wasn't taught how to determine whether or not a number is a prime during his whole 11 years in the public school system <3
Keep in mind this is the same zalzane who is in 11th grade and wasn't taught how to determine whether or not a number is a prime during his whole 11 years in the public school system <3

 Posts: 213
 Joined: Wed Sep 10, 2008 3:54 am UTC
Re: Consequences to P=NP
We can't assume it's a bad joke, because if you were serious you'd feel bad. We can't assume you're serious, because if you were joking you'd feel patronized.
It's a quantum indeterminacy problem, and therefore theoretically unresolvable.
It's a quantum indeterminacy problem, and therefore theoretically unresolvable.
Re: Consequences to P=NP
I thought it was funny. I almost smiled.
Re: Consequences to P=NP
P!=NP has little pratical implication because just knowing that a problem is polynomial tells you nothing about the degree of the polynomial. Theres no difference in practice between a problem with nonpolynomial complexity and one with complexity O(n^(10↑↑↑↑↑↑10)).
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Consequences to P=NP
poohat wrote:P!=NP has little pratical implication because just knowing that a problem is polynomial tells you nothing about the degree of the polynomial. Theres no difference in practice between a problem with nonpolynomial complexity and one with complexity O(n^(10↑↑↑↑↑↑10)).
For nearly all well behaved algorithim's, the degrees and coefficients of the polynomials is small.
Who is online
Users browsing this forum: No registered users and 3 guests