NP-

From JargonWiki

The Jargon File Parts of this article are based on the Jargon File, v. 4.4.7, a public domain document of hacker jargon.

NP-

/N·P/ Usage: pref.

NP-: /N·P/ pref.

Extremely. Used to modify adjectives describing a level or quality of difficulty; the connotation is often `more so than it should be'. This is generalized from the computer-science terms NP-hard and NP-complete; NP-complete problems all seem to be very hard, but so far no one has found a proof that they are. NP is the set of Nondeterministic-Polynomial problems, those that can be completed by a nondeterministic Turing machine in an amount of time that is a polynomial function of the size of the input; a solution for one NP-complete problem would solve all the others. "Coding a BitBlt implementation to perform correctly in every case is NP-annoying."

Note, however, that strictly speaking this usage is misleading; there are plenty of easy problems in class NP. NP-complete problems are hard not because they are in class NP, but because they are the hardest problems in class NP.

Sources

Public Domain This article is in the public domain and is not subject to copyright, trademark, or any other legal protection of intellectual property. Any and all user contributions to this page are also immediately dedicated to the public domain. Editors of this page must accede to these terms as special conditions of the standard editing privileges.