5 ms·

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

• 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."