Definitions

from Wiktionary, Creative Commons Attribution/Share-Alike 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 NP-complete graph problems (which I cannot do myself).

    Bunny and a Book

  • I think porn was proven to be "NP-complete" a while ago.

    Porn or Not Dot Com

  • Computing the conditions for fine tuning based on landscape arguments is likely an NP-complete 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 NP-complete.

    Archive 2008-05-01

  • What has happened here is that, as computer science tries to understand ai it has realized that many aspects of ai are NP-complete or NP-hard, and a few aspects are not.

    2008 November « Tai-Chi Policy

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

    The Father of Quantum Computing

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

    On the Long-awaited Cusp of a New Generation in Computing

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

    July 2005

  • And, incidentally, looks a lot like the usual situation when heuristics can solve NP-complete problems.

    Obsessively barking up the wrong tree - The Panda's Thumb

  • NP-complete problem using a construction of rods and balls (Vergis et.al. 1986) that unfortunately ignores the accumulating time-delays in the rigid rods that result in an exponential overall slowdown.

    Quantum Computing

Wordnik is becoming a not-for-profit! Read our announcement here.

Comments

Log in or sign up to get involved in the conversation. It's quick and easy.