Definitions
from Wiktionary, Creative Commons Attribution/ShareAlike License
 adj. Describing the hardest problems that are in the class NP, and whose solutions can be verified in polynomial time.
Etymologies
Sorry, no etymologies found.
Examples

Slime mold is capable of solving NPcomplete graph problems (which I cannot do myself).

I think porn was proven to be "NPcomplete" a while ago.

Computing the conditions for fine tuning based on landscape arguments is likely an NPcomplete problem.
If We Live in a Multiverse, How Many Are There?  Universe Today

In the meantime, although the game seems quite stark and simple, it's entirely possible that it's NPcomplete.

What has happened here is that, as computer science tries to understand ai it has realized that many aspects of ai are NPcomplete or NPhard, and a few aspects are not.

Spooky Computing Quantum computers hold the possibility of solving what computer science calls "NPcomplete" problems, the problems that are impossible or nearly impossible to calculate on a classical computer.

Regardless, the properties of quantum tunneling allows Orion to tackle a limited type of NPcomplete problems – a particularly tedious type problem first proposed by Stephen Cook in 1971.

May be a bit technical for lay people, what with all the talk about NPcomplete problems, but still, it's quite an interesting story.

And, incidentally, looks a lot like the usual situation when heuristics can solve NPcomplete problems.

NPcomplete problem using a construction of rods and balls (Vergis et.al. 1986) that unfortunately ignores the accumulating timedelays in the rigid rods that result in an exponential overall slowdown.
Comments
Log in or sign up to get involved in the conversation. It's quick and easy.