non from FOLDOC

non-algorithmic procedure

non-constructive proof

(Or "existence proof") A proof that something exists that does not provide an example of that thing or a method for finding an example. (A constructive proof does provide such an example or method).

For example, for any pair of finite real numbers n < 0 and p > 0 there exists a real number 0 < k < 1 such that

 f(k) = (1-k)*n + k*p = 0.

A non-constructive proof might proceed by observing that as k changes continuously from 0 to 1, f(k) changes continuously from n to p and, since they lie either side of zero, f(k) must pass through zero for some intermediate value of k. This proof does not tell us what that value of k is, only that it exists.

Cantor's proof that the real numbers are uncountable can be thought of as a non-constructive proof that irrational numbers exist. There are existence theorems with no known constructive proof.

Last updated: 2014-08-23

nondeterminism

<algorithm>

A property of a computation which may have more than one result.

One way to implement a nondeterministic algorithm is using backtracking, another is to explore (all) possible solutions in parallel.

Last updated: 1995-04-13

nondeterministic

Exhibiting nondeterminism.

nondeterministic automaton

<theory>

(Or "probabilistic automaton") An automaton in which there are several possible actions (outputs and next states) at each state of the computation such that the overall course of the computation is not completely determined by the program, the starting state, and the initial inputs.

Last updated: 1996-05-07

nondeterministic polynomial time

<complexity>

(NP) A set or property of computational decision problems solvable by a nondeterministic Turing Machine in a number of steps that is a polynomial function of the size of the input. The word "nondeterministic" suggests a method of generating potential solutions using some form of nondeterminism or "trial and error". This may take exponential time as long as a potential solution can be verified in polynomial time.

NP is obviously a superset of P (polynomial time problems solvable by a deterministic Turing Machine in polynomial time) since a deterministic algorithm can be considered as a degenerate form of nondeterministic algorithm. The question then arises: is NP equal to P? I.e. can every problem in NP actually be solved in polynomial time? Everyone's first guess is "no", but no one has managed to prove this; and some very clever people think the answer is "yes".

If a problem A is in NP and a polynomial time algorithm for A could also be used to solve problem B in polynomial time, then B is also in NP.

Nondeterministic Turing Machine

<complexity>

A normal (deterministic) Turing Machine that has a "guessing head" - a write-only head that writes a guess at a solution on the tape first, based on some arbitrary internal algorithm. The regular Turing Machine then runs and returns "yes" or "no" to indicate whether the solution is correct.

A nondeterministic Turing Machine can solve nondeterministic polynomial time computational decision problems in a number of steps that is a polynomial function of the size of the input

Last updated: 1995-04-27

non-impact printer

<printer>

Any printer, such as a laser printer, ink-jet printer, LED page printer, that prints without striking the paper, unlike a dot matrix printer which hits the paper with small pins. Non-impact printers are quieter than impact printers, and also faster due the lack of moving parts in the print head.

Last updated: 1995-11-20

non-interlaced

interlace

nonintrusive testing

<testing>

Testing that is transparent to the software under test, i.e., does not change its timing or processing characteristics. Nonintrusive testing usually involves additional hardware that collects timing or processing information and processes that information on another platform.

nonlinear

(Scientific computation) A property of a system whose output is not proportional to its input. For example, a transistor has a region of input voltages for which its output voltage is found by multiplying the input voltage by the gain of the transistor. Outside this region though, the transistor behaves non-linearly, meaning that it does not obey this simple equation. The behaviour of a system containing non-linear components is thus harder to model and to predict.

[Jargon File]

Non-Maintainer Upload

<operating system>

(NMU) A release of a Debian package by someone other than its usual maintainer. E.g. "The bug was fixed in a recent NMU."

Last updated: 2014-09-30

Non-Maskable Interrupt

(NMI) An IRQ 7 on the PDP-11 or 680x0 or the NMI line on an 80x86. In contrast with a priority interrupt (which might be ignored, although that is unlikely), an NMI is *never* ignored.

Last updated: 1994-12-13

non-optimal solution

(Or "sub-optimal solution") An astoundingly stupid way to do something. This term is generally used in deadpan sarcasm, as its impact is greatest when the person speaking looks completely serious.

Nonpareil

One of five pedagogical languages based on Markov algorithms, used in ["Nonpareil, a Machine Level Machine Independent Language for the Study of Semantics", B. Higman, ULICS Intl Report No ICSI 170, U London (1968)]. The others were Brilliant, Diamond, Pearl and Ruby.

non parity

parity

non-polynomial

<complexity>

The set or property of problems for which no polynomial-time algorithm is known.

This includes problems for which the only known algorithms require a number of steps which increases exponentially with the size of the problem, and those for which no algorithm at all is known. Within these two there are problems which are "provably difficult" and "provably unsolvable".

Last updated: 1995-04-10

Non Return to Zero Inverted

<storage>

(NRZI) A recording method used for 9-track magnetic tapes (200 and 800 BPI) where a zero is represented by a change in the signal and a one by no change.

NRZI is also used extensively in SDLC communications. VTAM has a parameter NRZI=YES|NO.

Compare Phase Encoded, GCR.

Last updated: 1999-01-11

nontrivial

Requiring real thought or significant computing power. Often used as an understated way of saying that a problem is quite difficult or impractical, or even entirely unsolvable ("Proving P=NP is nontrivial"). The preferred emphatic form is "decidedly nontrivial".

See uninteresting, interesting.

[Jargon File]

Last updated: 1995-02-21

Non-Uniform Memory Access

<architecture>

(NUMA) A memory architecture, used in multiprocessors, where the access time depends on the memory location. A processor can access its own local memory faster than non-local memory (memory which is local to another processor or shared between processors).

Last updated: 1995-11-12

non-uniform quantising logarithmic compression

The kind of compression often applied to a sound waveform. Logarithmic compression is a good match for the human ear's sensitivity but cannot handle zero amplitude (for which the logarithm is negative infinity). There are two standard compression functions which give a smooth transition between the logarithmic function and a linear segment passing through the origin: mu-law (North America) and A-law (ITU-T).

Last updated: 1995-02-21

Non-Uniform Rational B Spline

<graphics, mathematics>

(nurbs) A common term in Mechanical CAD. The NURBS has excellent continuity characteristics which make it useful for creating accurate models in 3D geometry generation and computer modelling.

[What is a nurbs? an rbs? a bs? a s?]

Last updated: 1996-08-27

non-volatile

non-volatile storage

non-volatile memory

non-volatile storage

Non-Volatile Random Access Memory

<storage>

(NVRAM) Static random-access memory which is made into non-volatile storage either by having a battery permanently connected or by saving its contents to EEPROM before turning the power off and reloading it when power is restored.

Last updated: 1995-04-22

non-volatile storage

<storage>

(NVS, persistent storage, memory) A term describing a storage device whose contents are preserved when its power is off. Storage using magnetic media (e.g. magnetic disks, magnetic tape or bubble memory) is normally non-volatile by nature whereas semiconductor memories (static RAM and especially dynamic RAM) are normally volatile but can be made into non-volatile storage by having a (rechargable) battery permanently connected.

Dynamic RAM is particularly volatile since it looses its data, even if the power is still on, unless it is refreshed. An acoustic delay line is a (very old) example of a volatile storage device.

Other examples of non-volatile storage are EEPROM, CD-ROM, paper tape and punched cards.

Last updated: 2000-05-22

Nearby terms:

Nominal Semidestructor ♦ non-algorithmic procedure ♦ non-constructive proof

Try this search on Wikipedia, Wiktionary, Google, OneLook.