FANDOM


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

"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).

Pages in category "P≠NP"

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.