## Consequences to P=NP

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

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)?

Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

### Re: Consequences to P=NP

Generally speaking, the reason e-commerce would collapse is that cryptography would collapse. No one's going to buy anything over the internet if their credit-card 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 non-deterministic algorithm that always solves it in polynomial time. (NP stands for non-deterministic 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.

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### 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 NP-complete. In other words, a polynomial time algorithm may exist for factoring even if P!=NP. And RSA is under attack even if factoring is NP-complete, because quantum computers, once they are scalable and feasible, can find a factor with polynomially high probability, since there is a polynomial-size 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.

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### 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 quantum-coherent devices with computers"

Nath
Posts: 3148
Joined: Sat Sep 08, 2007 8:14 pm UTC

### 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 #P-complete. (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.)

Anjruu
Posts: 19
Joined: Mon Jun 04, 2007 1:39 pm UTC

### Re: Consequences to P=NP

I don't know if there really would be any difference. There may be a way to solve 3-SAT given, say, a 200-dimension 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 NP-complete problem, so we still would be using approximation algorithms that run in a reasonable amount of time

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### 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.)

Nath
Posts: 3148
Joined: Sat Sep 08, 2007 8:14 pm UTC

### 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 NP-hard 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 guarantee-less algorithms for these problems, they don't always find a solution.)

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

### Re: Consequences to P=NP

Briareos wrote:Generally speaking, the reason e-commerce would collapse is that cryptography would collapse. No one's going to buy anything over the internet if their credit-card 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 non-deterministic algorithm that always solves it in polynomial time. (NP stands for non-deterministic 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 non-polynomial 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 non-polynomial 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 non-polynomial 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.

Spoiler:
This is such a physicist MO: First you make an outrageous Taylor expansion, then you claim everything else (a.k.a. reality) is a special case.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

stephentyrone
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 non-polynomial, but nondeterministic-polynomial, which means a nondeterministic turing machine could do the algorithm in polynomial time. For example, a non-deterministic 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 highest-ranking polynomial. This means all polynomials can be written a O(n^k) in big oh notation. Since the fastest-growing 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.

/\/_\/\/
Posts: 2
Joined: Wed Apr 22, 2009 2:38 am UTC
Location: New York

### 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).

stephentyrone
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.

samk
Posts: 54
Joined: Mon Feb 09, 2009 12:33 pm UTC

### 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.

andy33gmail
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 meta-proof (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.

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)⚠);}`
[he/him/his]

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 second-order 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.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

### 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.

andy33gmail
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 3-SAT problem we throw at them but we can't prove they'll always work.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

### 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 3-SAT 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.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

### Re: Consequences to P=NP

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.

GenericPersonTypeObject
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.

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.
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.

Agent_Irons
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 fifty-proof.

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)⚠);}`
[he/him/his]

zalzane
Posts: 41
Joined: Sat Apr 25, 2009 5:17 am UTC

### Re: Consequences to P=NP

is 1 a whole number?

P=NP

P=5 (or any other whole number)
N=1

5=(1)(5)

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

### 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.

zalzane
Posts: 41
Joined: Sat Apr 25, 2009 5:17 am UTC

### 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.

andy33gmail
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 semi-decent 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?
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.

zalzane
Posts: 41
Joined: Sat Apr 25, 2009 5:17 am UTC

### 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

Agent_Irons
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.

InkL0sed
Posts: 205
Joined: Wed Sep 10, 2008 3:46 am UTC

### Re: Consequences to P=NP

I thought it was funny. I almost smiled.

poohat
Posts: 230
Joined: Mon Apr 07, 2008 6:21 am UTC

### 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 non-polynomial 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 non-polynomial 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.

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga