Retrologic Systems Retrologic Systems Retrologic Systems
Online Jargon File
  RetroGuard  |  RetroCapture  |  Contracting  |  Site Map  |  Contact

NP- - The Jargon File

0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Jargon On Your Website    Random Entry (Alt-R)RSS Feed - Random Jargon
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.


 
 Copyright © 1998-2006 Retrologic Systems. retroguard | retrocapture | contracting | site map | contact
 All rights reserved. site terms | privacy policy