5 ms·
How does one go about showing that there is no way to solve such a problem? What about the argument that perhaps the author was not clever enough to devise an
by codeodor 17y ago
How does one go about showing that there is no way to solve such a problem?
What about the argument that perhaps the author was not clever enough to devise an algorithm which solves the problem he stated?
Perhaps when I read the papers I will be enlightened?
- cperciva 17y agoHow does one go about showing that there is no way to solve such a problem? With great difficulty. Usually the approach is to suppose that you have an algorithm and show that either (a) this algorithm allows you to do something impossible (e.g., solve a different impossible problem, or reach a contradiction); or (b) there are two different problems with different answers which the specified algorithm cannot distinguish between (this is generally only possible where you're proving that it's impossible to compute something in less than some number of steps). The first approach is used for things like showing that the halting problem is impossible; the second approach is used for things like showing that it's impossible to have a comparison sort which runs in less than O(N log N) time.
- codeodor 17y agoActually, now that you mention it I can recall these. Thanks for the refresher!