4 ms·

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 unscientifi

by skissane 11mo 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 11mo 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 11mo 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 11mo 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 11mo 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.

fjfaase 11mo 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 11mo 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 11mo 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 11mo 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.