Wikipedia:NP (complexity) and Wikipedia:P versus NP problem are good starting points for fairly thorough discussions of the issues. Note that my own discussion below seems to make the issue harder to resolve, but sheds some critical light on just how difficult the question may actually be.
The diagram immediately below would seem to indicate that "NP-hard" problems may have a greater number of dimensions than we can ever reach. We could define NP-hard as being simply beyond the computing power that could ever, even theoretically, be available to us, though the actual difficulty of any problem in the class would have to constantly be revised as our computing power grows.
"P np np-complete np-hard" by Behnam Esfahbod. Licensed under CC BY-SA 3.0 via Commons - https://commons.wikimedia.org/wiki/File:P_np_np-complete_np-hard.svg#/media/File:P_np_np-complete_np-hard.svg
| This page uses Creative Commons Licensed content from Wikipedia (view authors). |
All items (1)
