: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' (NP-complete problems all seem
to be very hard, but so far no one has found a good a priori
reason that they should be.) "Coding a BitBlt implementation to
perform correctly in every case is NP-annoying." This is
generalized from the computer-science terms `NP-hard' and
`NP-complete'. NP is the set of Nondeterministic-Polynomial
algorithms, 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. Note, however, that the NP- prefix is,
from a complexity theorist's point of view, the wrong part of
`NP-complete' to connote extreme difficulty; it is the completeness,
not the NP-ness, that puts any problem it describes in the
`hard' category.
-- The AI Hackers Dictionary
describing a level or quality of difficulty; the connotation is
often `more so than it should be' (NP-complete problems all seem
to be very hard, but so far no one has found a good a priori
reason that they should be.) "Coding a BitBlt implementation to
perform correctly in every case is NP-annoying." This is
generalized from the computer-science terms `NP-hard' and
`NP-complete'. NP is the set of Nondeterministic-Polynomial
algorithms, 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. Note, however, that the NP- prefix is,
from a complexity theorist's point of view, the wrong part of
`NP-complete' to connote extreme difficulty; it is the completeness,
not the NP-ness, that puts any problem it describes in the
`hard' category.
-- The AI Hackers Dictionary
Related:
- 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... - AI-complete /A-I k*m-pleet'/ adj.
[MIT, Stanford:
by analogy with `NP-complete' (see NP-)] Used to... - AI-complete: /A-I k*m-pleet'/ [MIT, Stanford: by analogy with
`NP-complete' (see {NP-})] adj.
Used to describe problems or subproblems in AI,... - brute force adj.
Describes a primitive programming style,
one in which the programmer relies on the computer's... - At about 2500 A.D., humankind discovers a computer problem that *must* be
solved.
The only difficulty is that the problem is NP complete... - The algorithm for finding the longest path in a graph is NP-complete.
For you systems people, that means it's *real slow*... - proof by personal communication:
'Eight-dimensional colored cycle stripping is NP-complete
[Karp,
personal communication].' proof by reduction to the... - nontrivial: adj. Requiring real thought or significant computing
power.
Often used as an understated way of saying that a problem... - proof by obfuscation:
A long plotless sequence of true and/or meaningless
syntactically related statements.
proof by wishful citation: The author cites the...
