|
Tiny Bug Child posted:b/c all you would have to do to prove it is find a polynomial time algorithm, no matter how slow or lovely, for any problem in NP, and lots of smart people have been trying to do that for decades while getting nowhere. also P != NP is the intuitive answer. i mean if you think about the problems involved it's pretty obvious there are no easy solutions for them. i have no idea how anyone could think P = NP tbh Yeah: proving theorems in a formal system is an NP problem, so P=NP is roughly equivalent to saying "maths is secretly easy". I recently found out that we already have an algorithm for some NP-complete problem that we can show runs in polynomial time iff P=NP, but no-one can prove anything about its worst-case asymptotic behaviour.
|
# ¿ May 16, 2017 10:16 |
|
|
# ¿ May 14, 2024 11:19 |