5 ms·

The fact that thousands of people have failed to prove that P=NP indication that it is probably not true. It has even been proven that it cannot be proven by so

by fjfaase 10mo ago

The fact that thousands of people have failed to prove that P=NP indication that it is probably not true. It has even been proven that it cannot be proven by some methods.

ahmedfromtunis 10mo ago
This is a fairly new question; from the early 20th century, iirc. There were many questions with no answers for literal centuries and thousands trying, and failing, to crack them. A solution was ultimately found despite that. A new "math" might be needed, but an answer (affirming or not) will be found.
- fjfaase 10mo ago
  It is fairly new, but very relevant for daily life, like many others are not. Thousands of people have tried to write smart algorithms to solve NP problems and many have thought they found an algorithm in P only to be disproven later. Whether the Riemann hypotesis is true or not, is not going to have any practical effect, accept for a small group of mathematisians who are working on it. Most people do not know what a Field medal is nor care about it.
- skissane 10mo ago
  > A new "math" might be needed, but an answer (affirming or not) will be found. What if there exists a proof that P!=NP, but the shortest possible proof of that proposition is a googolplex symbols that long? Then P!=NP would be true, and provable and knowable in theory, yet eternally unprovable and unknowable in practice
  - ahmedfromtunis 10mo ago
    That's exactly the kind of situation I had in mind when I wrote that. Goodstein’s theory would take more symbols than there are atoms in the observable universe to write down in "classic" maths. To "fix" this, mathematicians had to use a "new" way of thinking about infinity known as transfinite induction. I think if we're smart enough to detect(?) a proof, we'll find a way to express it in a finite manner.
skissane 10mo ago
Couldn’t you equally say “The fact that thousands of people have failed to prove that P!=NP indication that it is probably not true”? My completely unscientific hunch is someone will eventually prove that P=?=NP is independent of ZF(C). Maybe the universe just really wants to mess with complexity theorists
- fjfaase 10mo ago
  Maybe I should have written: "Many have tried to find algorithms in P to solve NP problems and failed to find them." Even now, many people are working on algorithms to find solutions for NP problems. I understand that it has been proven that it is not possible to proof P=NP? using 'algorithms'. That might mean that even when a proof is found that P=NP that there still will be no P algorithm to solve NP problems.
  - skissane 10mo ago
    Someone might eventually provide a non-constructive proof that P=NP - a proof that such an algorithm must exist but which fails to actually produce one. Or even a galactic algorithm-an algorithm for solving an NP-complete problem that is technically in P, but completely useless for anything in practice, e.g. O(n^10000000)
    - IAmBroom 10mo ago
      > solving an NP-complete problem that is technically in P, but completely useless for anything in practice So it's P and NP. (Edit: I keep misphrasing this!) P ?= NP is not about ease, nor even realistic efforts.
- wjnc 10mo ago
  My philosophy of math muscles tingle at both sentences at about the same rate. P=NP and P=!NP are both proven nor disproven. (There is redundant information in this sentence.) History shows us that the historical / ‘effort’ argument is not applicable to mathematics. All proofs were unproven once until proven successfully for the first time. Harder problems need bigger shoulders to stand on. Sometimes this is due to new tools, sometimes it is a magically gifted individual focusing on the problem, usually some mix of both. All we know is that all before have failed. It’s one of the beauties in math.
nrhrjrjrjtntbt 10mo ago
P=NP feels like too much of a free lunch. Yeah thats unscientific but a hunch.
- skissane 10mo ago
  It needn’t be a “free lunch” at all. An O(n^1000) algorithm for an NP-complete problem would constructively prove that P=NP yet be completely useless for solving any NP problems in practice

by fjfaase 10mo ago

The fact that thousands of people have failed to prove that P=NP indication that it is probably not true. It has even been proven that it cannot be proven by some methods.

ahmedfromtunis 10mo ago

This is a fairly new question; from the early 20th century, iirc. There were many questions with no answers for literal centuries and thousands trying, and failing, to crack them. A solution was ultimately found despite that. A new "math" might be needed, but an answer (affirming or not) will be found.

fjfaase 10mo ago
It is fairly new, but very relevant for daily life, like many others are not. Thousands of people have tried to write smart algorithms to solve NP problems and many have thought they found an algorithm in P only to be disproven later. Whether the Riemann hypotesis is true or not, is not going to have any practical effect, accept for a small group of mathematisians who are working on it. Most people do not know what a Field medal is nor care about it.
skissane 10mo ago
> A new "math" might be needed, but an answer (affirming or not) will be found. What if there exists a proof that P!=NP, but the shortest possible proof of that proposition is a googolplex symbols that long? Then P!=NP would be true, and provable and knowable in theory, yet eternally unprovable and unknowable in practice
- ahmedfromtunis 10mo ago
  That's exactly the kind of situation I had in mind when I wrote that. Goodstein’s theory would take more symbols than there are atoms in the observable universe to write down in "classic" maths. To "fix" this, mathematicians had to use a "new" way of thinking about infinity known as transfinite induction. I think if we're smart enough to detect(?) a proof, we'll find a way to express it in a finite manner.

skissane 10mo ago

Couldn’t you equally say “The fact that thousands of people have failed to prove that P!=NP indication that it is probably not true”? My completely unscientific hunch is someone will eventually prove that P=?=NP is independent of ZF(C). Maybe the universe just really wants to mess with complexity theorists

fjfaase 10mo ago
Maybe I should have written: "Many have tried to find algorithms in P to solve NP problems and failed to find them." Even now, many people are working on algorithms to find solutions for NP problems. I understand that it has been proven that it is not possible to proof P=NP? using 'algorithms'. That might mean that even when a proof is found that P=NP that there still will be no P algorithm to solve NP problems.
- skissane 10mo ago
  Someone might eventually provide a non-constructive proof that P=NP - a proof that such an algorithm must exist but which fails to actually produce one. Or even a galactic algorithm-an algorithm for solving an NP-complete problem that is technically in P, but completely useless for anything in practice, e.g. O(n^10000000)
  - IAmBroom 10mo ago
    > solving an NP-complete problem that is technically in P, but completely useless for anything in practice So it's P and NP. (Edit: I keep misphrasing this!) P ?= NP is not about ease, nor even realistic efforts.
wjnc 10mo ago
My philosophy of math muscles tingle at both sentences at about the same rate. P=NP and P=!NP are both proven nor disproven. (There is redundant information in this sentence.) History shows us that the historical / ‘effort’ argument is not applicable to mathematics. All proofs were unproven once until proven successfully for the first time. Harder problems need bigger shoulders to stand on. Sometimes this is due to new tools, sometimes it is a magically gifted individual focusing on the problem, usually some mix of both. All we know is that all before have failed. It’s one of the beauties in math.

nrhrjrjrjtntbt 10mo ago

P=NP feels like too much of a free lunch. Yeah thats unscientific but a hunch.

skissane 10mo ago
It needn’t be a “free lunch” at all. An O(n^1000) algorithm for an NP-complete problem would constructively prove that P=NP yet be completely useless for solving any NP problems in practice