15 lines
2.6 KiB
HTML
15 lines
2.6 KiB
HTML
<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?>
|
||
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>NP-</title><link rel="stylesheet" href="../../jargon.css" type="text/css"/><meta name="generator" content="DocBook XSL Stylesheets V1.61.0"/><link rel="home" href="../index.html" title="The Jargon File"/><link rel="up" href="../N.html" title="N"/><link rel="previous" href="notwork.html" title="notwork"/><link rel="next" href="NSA-line-eater.html" title="NSA line eater"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">NP-</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="notwork.html">Prev</a> </td><th width="60%" align="center">N</th><td width="20%" align="right"> <a accesskey="n" href="NSA-line-eater.html">Next</a></td></tr></table><hr/></div><dt><a id="NP-"/><dt xmlns="" id="NP-"><b>NP-</b>: <span xmlns="http://www.w3.org/1999/xhtml" class="pronunciation">/N·P/</span>, <span xmlns="http://www.w3.org/1999/xhtml" class="grammar">pref.</span></dt></dt><dd><p> 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 <span class="firstterm">NP-hard</span> and <span class="firstterm">NP-complete</span>; 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. “<span class="quote">Coding a BitBlt
|
||
implementation to perform correctly in every case is
|
||
NP-annoying.</span>”</p><p>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.</p></dd><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="notwork.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="../N.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="NSA-line-eater.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">notwork </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> NSA line eater</td></tr></table></div></body></html>
|