3 ms·

Math is also useful. If someone showed that p = np tomorrow in a formally verified proof I don't care if no one can understand it.

by noosphr 1mo ago

chongli 1mo ago
A proof by contradiction that p = np is of no use to anyone, given that it wouldn't help you find any polynomial time algorithms for np-hard problems.
- ziiinq 1mo ago
  I don’t recall anything specific off the top of my head but I am confident that such a proof would have immediate actionable implications. Furthermore, careful analysis of the latter would as likely as not yield further understanding and, actually /would/ help finding such algorithms. Finally, it has been observed time and time again that often (again, nothing comes up and i don’t want to ask AI) the certainty that something is possible and has been done is motivation and inspiration enough for people to independently solve a problem. Sometimes it is even enough for someone new to simply not know that something is “hard” to solve. It even “motivates” llms, it seems (eg https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_prompt.pdf https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98...) Of course this is all pure speculation concerning a hypothetical proof that most likely doesn’t exist, or indeed might be so complicated as to not be approachable even after hundreds of lifetimes of study. Nevertheless your conclusion does not follow from the premise
- Jensson 1mo ago
  A proof that they are the same is of no use either, since it too wouldn't help you find algorithms that are faster. You would need an algorithm that finds solutions, not just a proof they exist. So the value here would almost entirely come from how you proved p = np, since that proof will probably be the first step towards finding the polynomial solutions. But if humans don't understand it good luck finding any.
- zmgsabst 1mo ago
  Abstract polynomial algorithms are of no use either, eg, translation may require galactic constants or high powers that are still intractable. We only compute with two kinds of things: - small data; or, - extremely lower power and coefficient algorithms We lack the power to, eg, use a quintic algorithm in anything but nearly trivial cases.
- shakow 1mo ago
  I don't think a proof that P = or ≠ NP would give you any polynomial-time algos for arbitrary problems either.
deleted 1mo ago
[deleted]
Scarblac 1mo ago
How would the mere knowledge that it holds, without any understanding why, be useful?
- ziiinq 1mo ago
  [dead]
- a2ff6eeb0 1mo ago
  Can you explain to your cat how Amazon uses graph theory to deliver their packages of cat food? Is Amazon still delivering food to your cat? Humans don't need to understand what AI generates. We still can get the rewards.
  - cindyllm 1mo ago
    [dead]
  - Jensson 1mo ago
    p = np doesn't produce any value though, the stuff you learn solving it might but the fact that they are the same wouldn't be valuable at all.
    - a2ff6eeb0 1mo ago
      sure, agreed, but once you have a proof, you can probably get AI to reduce other problems to that problem in P.
      - Jensson 1mo ago
        Why wouldn't you be able to do that without a proof? I don't see the value of the proof here, just ask the AI to solve the problem you want and the proof isn't needed.
        a2ff6eeb0 1mo ago
        From my understanding, the two are equivalent; if you can reduce an NP problem to a P problem, you've proven P=NP. The rest is application.
HWR_14 1mo ago
If a magic oracle tells you p=np, that's useless. How would that change anything?
- czgov 1mo ago
  If it’s an oracle and we know it’s an oracle then it’s not useless. Humans make mistake and there are examples of published results that were widely believed to be correct by experts that later proved to be wrong. Why do you think human verified proofs are better than machine verified proofs? Suppose an oracle tells us the Riemann Hypothesis is correct. There are a vast number of results of the form: If RH is correct then A. It would be very useful to have an oracle tells us whether or not RH is correct.
  - Jensson 1mo ago
    > It would be very useful to have an oracle tells us whether or not RH is correct. For what? Which product becomes better if it is correct?
    - czgov 1mo ago
      You have an unfortunate view of the value of knowledge. The frontiers of science would be static if everyone believed as you do.
      - deleted 1mo ago
        [deleted]
      - Jensson 1mo ago
        The whole point why anyone cares about these proofs is that the things we learn as we make the proof might add value, proving p = np itself isn't interesting, that knowledge has no application and therefore no value in itself. I have published mathematics so I do value knowledge, but for most of mathematics the value of the knowledge isn't the thing you try to prove it is all the things you learn as you try to prove it. p = np is one such thing. So the whole interesting bit about it is the proof, not the fact.
podocarp 1mo ago
Both are right. Practically speaking your view is right, and is similar to one of hilberts quest to come up with a proof spitting machine. Just get a computer to enumerate through all proofs and we absorb the results. But you have to agree this is deeply dissatisfying intellectually. This is like if trigonometry was discovered with no relation to circles and triangles but just as a series of look up tables (like in a calculator) and we just know it works for certain scenarios and that's all there is to it.

Math is also useful. If someone showed that p = np tomorrow in a formally verified proof I don't care if no one can understand it.

by noosphr 1mo ago

Math is also useful. If someone showed that p = np tomorrow in a formally verified proof I don't care if no one can understand it.

chongli 1mo ago

A proof by contradiction that p = np is of no use to anyone, given that it wouldn't help you find any polynomial time algorithms for np-hard problems.

ziiinq 1mo ago
I don’t recall anything specific off the top of my head but I am confident that such a proof would have immediate actionable implications. Furthermore, careful analysis of the latter would as likely as not yield further understanding and, actually /would/ help finding such algorithms. Finally, it has been observed time and time again that often (again, nothing comes up and i don’t want to ask AI) the certainty that something is possible and has been done is motivation and inspiration enough for people to independently solve a problem. Sometimes it is even enough for someone new to simply not know that something is “hard” to solve. It even “motivates” llms, it seems (eg https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_prompt.pdf https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98...) Of course this is all pure speculation concerning a hypothetical proof that most likely doesn’t exist, or indeed might be so complicated as to not be approachable even after hundreds of lifetimes of study. Nevertheless your conclusion does not follow from the premise
Jensson 1mo ago
A proof that they are the same is of no use either, since it too wouldn't help you find algorithms that are faster. You would need an algorithm that finds solutions, not just a proof they exist. So the value here would almost entirely come from how you proved p = np, since that proof will probably be the first step towards finding the polynomial solutions. But if humans don't understand it good luck finding any.
zmgsabst 1mo ago
Abstract polynomial algorithms are of no use either, eg, translation may require galactic constants or high powers that are still intractable. We only compute with two kinds of things: - small data; or, - extremely lower power and coefficient algorithms We lack the power to, eg, use a quintic algorithm in anything but nearly trivial cases.
shakow 1mo ago
I don't think a proof that P = or ≠ NP would give you any polynomial-time algos for arbitrary problems either.

deleted 1mo ago

[deleted]

Scarblac 1mo ago

How would the mere knowledge that it holds, without any understanding why, be useful?

ziiinq 1mo ago
[dead]
a2ff6eeb0 1mo ago
Can you explain to your cat how Amazon uses graph theory to deliver their packages of cat food? Is Amazon still delivering food to your cat? Humans don't need to understand what AI generates. We still can get the rewards.
- cindyllm 1mo ago
  [dead]
- Jensson 1mo ago
  p = np doesn't produce any value though, the stuff you learn solving it might but the fact that they are the same wouldn't be valuable at all.
  - a2ff6eeb0 1mo ago
    sure, agreed, but once you have a proof, you can probably get AI to reduce other problems to that problem in P.
    - Jensson 1mo ago
      Why wouldn't you be able to do that without a proof? I don't see the value of the proof here, just ask the AI to solve the problem you want and the proof isn't needed.
      - a2ff6eeb0 1mo ago
        From my understanding, the two are equivalent; if you can reduce an NP problem to a P problem, you've proven P=NP. The rest is application.

HWR_14 1mo ago

If a magic oracle tells you p=np, that's useless. How would that change anything?

czgov 1mo ago
If it’s an oracle and we know it’s an oracle then it’s not useless. Humans make mistake and there are examples of published results that were widely believed to be correct by experts that later proved to be wrong. Why do you think human verified proofs are better than machine verified proofs? Suppose an oracle tells us the Riemann Hypothesis is correct. There are a vast number of results of the form: If RH is correct then A. It would be very useful to have an oracle tells us whether or not RH is correct.
- Jensson 1mo ago
  > It would be very useful to have an oracle tells us whether or not RH is correct. For what? Which product becomes better if it is correct?
  - czgov 1mo ago
    You have an unfortunate view of the value of knowledge. The frontiers of science would be static if everyone believed as you do.
    - deleted 1mo ago
      [deleted]
    - Jensson 1mo ago
      The whole point why anyone cares about these proofs is that the things we learn as we make the proof might add value, proving p = np itself isn't interesting, that knowledge has no application and therefore no value in itself. I have published mathematics so I do value knowledge, but for most of mathematics the value of the knowledge isn't the thing you try to prove it is all the things you learn as you try to prove it. p = np is one such thing. So the whole interesting bit about it is the proof, not the fact.

podocarp 1mo ago

Both are right. Practically speaking your view is right, and is similar to one of hilberts quest to come up with a proof spitting machine. Just get a computer to enumerate through all proofs and we absorb the results. But you have to agree this is deeply dissatisfying intellectually. This is like if trigonometry was discovered with no relation to circles and triangles but just as a series of look up tables (like in a calculator) and we just know it works for certain scenarios and that's all there is to it.