4 ms·

when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assu

by hnben 3y ago

when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. <math stuff> 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false

beefield 3y ago
In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.
- hnben 3y ago
  > I would need to assume that I can solve a problem in polynomial time, and then find a contradiction iirc that's actually how many of these proofs work. > To me it is really hard to see a useful path forward from there. yes, CS is hard. there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS [1] https://www.quora.com/What-is-a-proof-by-contradiction-in-computational-complexity-theory https://www.quora.com/What-is-a-proof-by-contradiction-in-co...
- aatd86 3y ago
  If you see a path, you'll be one million USD richer. Don't forget about us. :-)
- tetha 3y ago
  That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno. This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements. A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."
perthmad 3y ago
Proving a negation is not a proof by contradiction, that's just the proof of an (absurd) implication. Logic people actually write blog posts about this: https://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ https://math.andrej.com/2010/03/29/proof-of-negation-and-pro...
- hnben 3y ago
  > I am discovering that mathematicians cannot tell the difference between “proof by contradiction” and “proof of negation”. I am glad to learn, that I just as dumb as the average mathematician lol. > Proving a negation is not a proof by contradiction did I say that it is, though?

by hnben 3y ago

beefield 3y ago

In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.

hnben 3y ago
> I would need to assume that I can solve a problem in polynomial time, and then find a contradiction iirc that's actually how many of these proofs work. > To me it is really hard to see a useful path forward from there. yes, CS is hard. there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS [1] https://www.quora.com/What-is-a-proof-by-contradiction-in-computational-complexity-theory https://www.quora.com/What-is-a-proof-by-contradiction-in-co...
aatd86 3y ago
If you see a path, you'll be one million USD richer. Don't forget about us. :-)
tetha 3y ago
That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno. This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements. A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."

perthmad 3y ago

Proving a negation is not a proof by contradiction, that's just the proof of an (absurd) implication. Logic people actually write blog posts about this: https://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ https://math.andrej.com/2010/03/29/proof-of-negation-and-pro...

hnben 3y ago
> I am discovering that mathematicians cannot tell the difference between “proof by contradiction” and “proof of negation”. I am glad to learn, that I just as dumb as the average mathematician lol. > Proving a negation is not a proof by contradiction did I say that it is, though?