4 ms·

Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we fi

by pdpi 10y ago

Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us. http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858

DavidSJ 10y ago
It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
- pdpi 10y ago
  With the caveat that it can never return false, which means it's not a complete solution.
- Klockan 10y ago
  This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
  - JadeNB 10y ago
    > This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1. That seems to be an argument for the uselessness of the distinction between P-with-large-exponent and not-P, not for the uselessness of having a reduction of NP to P. Also, it's worth noting that, if one is a theoretical computer scientist, then there is more of interest in the study of computing than what can be done in the universe. (I am a mathematician, and am, as I suspect most of my colleagues, serenely unconcerned with the applicability or non- of my work.)
  - paulddraper 10y ago
    It might be useless for solving NP problems, but that's not the "point" of P=NP per say. P=NP is an intrinsically interesting math problem. And the parent is pointing out that if P=NP, we already have a construction. So (if his opinion was presented accurately), Knuth is wrong about a positive proof being non-constructive. --- I believe there are already known problems whose best solution is O(n^k) for arbitrarily high k. So yeah, naturally not everything will be practically tractable.
  - qmalzp 10y ago
    If the minimum exponent of a problem as natural as 3-SAT ended up being ~1000, that might be even more fascinating than the fact that it's polynomial.
  - btilly 10y ago
    Your argument supports the view that P is a useless concept, not that that argument is pointless.
    - VLM 10y ago
      Often a "proof" that P does not equal NP is that it would be terribly inconvenient if solvable in n to the second or whatever, and therefore in a sort of cosmic censorship saves us by claiming it clearly can't be the case because it would be so annoying. A good argument can be provided by an analysis of statistical thermodynamics gas laws. It highly disturbs some people to think that atoms being in motion implies that all the oxygen atoms in the room air might coincidentally cluster into a small corner of the room leaving the victim to suffocate. There is no reason to think that impossible under most thermodynamics theories. However, it is nearly infinitely unlikely and you'd merely have to wait a ten to the hundred times the lifespan of the universe for it to coincidentally happen. I suppose it scales quite strongly with room volume and linearly with air pressure, you have one atom in the ISS airlock and being in one half the air lock at any given moment is a very predictable 50:50 odds... Likewise if the smallest polynomial solution to a NP problem takes a google's worth of universes to calculate, then even if it is poly you need not worry too much about mere human inconvenience. I'm not saying its a wise way to go thru life, but there exists a large set of people who get hung up on whats convenient or beautiful must be right, even if whats right turns out to be very ugly or inconvenient, so for them "P=NP but your bank account is still secure" is a very big deal.
- btilly 10y ago
  Fascinating. In fact by devoting half of its time to the first algorithm, a quarter to the second, and so on, it will solve it in the same big-O as the most efficient algorithm! (Albeit with a horrible constant.) That said, this algorithm does not solve the decision problem because it can never return a no. Only a yes if there is one to be found.
woliveirajr 10y ago
I love his timing: Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic
- OJFord 10y ago
  > by either 2048 or 4096 It's an odd statement for a mathematician/computer scientist. It's equivalent to "by 4096", surely.
  - Terr_ 10y ago
    Logically, you don't even need the first clause, since anything solved "by" the first milestone should remain and be solved "by" the second as well :p
    - OJFord 10y ago
      Yes, that's my point.
VLM 10y ago
That is one interesting way to interpret the famous Aaronson soap bubble experimental results, and Yuri Gurevich's opinion is just a somewhat more optimistic version of it. Because of some hand wavy string theory calculation completed in 2030, either the universe doesn't exist as it is measured to exist (or whatever McGuffin you'd like as a bullet proof excuse) or there exists a Turing machine that outputs a proof of P=NP then halts and the fastest way to find out if it halts is to run it and we try and it never stops. Maybe a century later someone figures out a lower bound on the number of steps the machine will make before it halts and its larger than the computational power of the lifetime of the universe, even very optimistically. Or a ruleset is proven to exist but the ruleset is at minimum a number larger than the number of particles in the universe so its kinda difficult to construct or emulate. Or the infinitely long Turing tape is merely proven to contain a number of states equal to a trillion times the number of atoms in the universe.

by pdpi 10y ago

DavidSJ 10y ago

It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...

pdpi 10y ago
With the caveat that it can never return false, which means it's not a complete solution.
Klockan 10y ago
This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
- JadeNB 10y ago
  > This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1. That seems to be an argument for the uselessness of the distinction between P-with-large-exponent and not-P, not for the uselessness of having a reduction of NP to P. Also, it's worth noting that, if one is a theoretical computer scientist, then there is more of interest in the study of computing than what can be done in the universe. (I am a mathematician, and am, as I suspect most of my colleagues, serenely unconcerned with the applicability or non- of my work.)
- paulddraper 10y ago
  It might be useless for solving NP problems, but that's not the "point" of P=NP per say. P=NP is an intrinsically interesting math problem. And the parent is pointing out that if P=NP, we already have a construction. So (if his opinion was presented accurately), Knuth is wrong about a positive proof being non-constructive. --- I believe there are already known problems whose best solution is O(n^k) for arbitrarily high k. So yeah, naturally not everything will be practically tractable.
- qmalzp 10y ago
  If the minimum exponent of a problem as natural as 3-SAT ended up being ~1000, that might be even more fascinating than the fact that it's polynomial.
- btilly 10y ago
  Your argument supports the view that P is a useless concept, not that that argument is pointless.
  - VLM 10y ago
    Often a "proof" that P does not equal NP is that it would be terribly inconvenient if solvable in n to the second or whatever, and therefore in a sort of cosmic censorship saves us by claiming it clearly can't be the case because it would be so annoying. A good argument can be provided by an analysis of statistical thermodynamics gas laws. It highly disturbs some people to think that atoms being in motion implies that all the oxygen atoms in the room air might coincidentally cluster into a small corner of the room leaving the victim to suffocate. There is no reason to think that impossible under most thermodynamics theories. However, it is nearly infinitely unlikely and you'd merely have to wait a ten to the hundred times the lifespan of the universe for it to coincidentally happen. I suppose it scales quite strongly with room volume and linearly with air pressure, you have one atom in the ISS airlock and being in one half the air lock at any given moment is a very predictable 50:50 odds... Likewise if the smallest polynomial solution to a NP problem takes a google's worth of universes to calculate, then even if it is poly you need not worry too much about mere human inconvenience. I'm not saying its a wise way to go thru life, but there exists a large set of people who get hung up on whats convenient or beautiful must be right, even if whats right turns out to be very ugly or inconvenient, so for them "P=NP but your bank account is still secure" is a very big deal.
btilly 10y ago
Fascinating. In fact by devoting half of its time to the first algorithm, a quarter to the second, and so on, it will solve it in the same big-O as the most efficient algorithm! (Albeit with a horrible constant.) That said, this algorithm does not solve the decision problem because it can never return a no. Only a yes if there is one to be found.

woliveirajr 10y ago

I love his timing: Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic

OJFord 10y ago
> by either 2048 or 4096 It's an odd statement for a mathematician/computer scientist. It's equivalent to "by 4096", surely.
- Terr_ 10y ago
  Logically, you don't even need the first clause, since anything solved "by" the first milestone should remain and be solved "by" the second as well :p
  - OJFord 10y ago
    Yes, that's my point.

VLM 10y ago

That is one interesting way to interpret the famous Aaronson soap bubble experimental results, and Yuri Gurevich's opinion is just a somewhat more optimistic version of it. Because of some hand wavy string theory calculation completed in 2030, either the universe doesn't exist as it is measured to exist (or whatever McGuffin you'd like as a bullet proof excuse) or there exists a Turing machine that outputs a proof of P=NP then halts and the fastest way to find out if it halts is to run it and we try and it never stops. Maybe a century later someone figures out a lower bound on the number of steps the machine will make before it halts and its larger than the computational power of the lifetime of the universe, even very optimistically. Or a ruleset is proven to exist but the ruleset is at minimum a number larger than the number of particles in the universe so its kinda difficult to construct or emulate. Or the infinitely long Turing tape is merely proven to contain a number of states equal to a trillion times the number of atoms in the universe.