5 ms·
Thank you- your link to non-constructive proofs led me to this HN comment, which seems to flesh out why such proofs are not applicable to P = NP https://news.y
by wddkcs 3y ago
Thank you- your link to non-constructive proofs led me to this HN comment, which seems to flesh out why such proofs are not applicable to P = NP
https://news.ycombinator.com/item?id=29022963 https://news.ycombinator.com/item?id=29022963
Im just reading about constructive vs. Non-constructive proofs, but my intuition seems to be that a proof would P = NP would have to be constructive.
https://news.ycombinator.com/item?id=19720511 https://news.ycombinator.com/item?id=19720511
- linkgoron 3y agoThat "proof" is applicable to any algorithm that "exists". As "an algorithm exists, so we can enumerate all of the Turing machines "in parallel" and find it" would work for anything in P, other algorithms as well. However, good luck actually running that algorithm... Enumerating Turing machines in parallel, executing them, and n could be many times larger than the age of the universe. You want something that you can execute, not something that in theory exists.
- Dylan16807 3y agoThe kind of ultra-shoddy "construction" you get from "Here is an impossible to build machine that would give us the proof" would still not get you a demonstration. It would still be something we don't have the algorithm for.