3 ms·
> Oh absolutely, you'd never want to run such a program. However, it's existence is a useful mathematical trick. This was the beginning of the thread: If you h
by seppel 3y ago
> Oh absolutely, you'd never want to run such a program. However, it's existence is a useful mathematical trick.
This was the beginning of the thread: If you have a non-constructive proof that P=NP, it still means you cannot solve all NP problems quickly until someone actually finds a program to do so.
- sebzim4500 3y agoAre you quoting someone? I did ctrl-f and found nothing.
- hnfong 3y agoIt's literally the first comment: https://news.ycombinator.com/item?id=37182868 https://news.ycombinator.com/item?id=37182868 I do agree the reply about brute forcing the solution space is a bit trollish, in the sense that while it does purport to provide a "constructive" way to find the polynomial time NP solver, it's not actually feasible. The sleight of hand is where it asserts that the length of the program is a "constant" -- which is technically true because it doesn't depend on the length of the NP problem they're trying to solve... but we're not trying to solve the NP problem, we're trying to find the solver for the NP problem. I'm no expert in all things NP, but the assumption that a polynomial time SAT solver (if it exists) would have a "normal" length seem to be a very suspect assumption.