In
Computer Science this is the class of
Problems, usually called
NP, for which a
non deterministic Turing machine (
NDTM) exists, which
worst case calculation time is
polynomial. It has been proven that
P (the same with
deterministic turing machines) is a subset or equal to
NP (P⊆NP).
Every
logarithmic t(n)
time-limited register machine can be simulated by a O(q(n+t(n))) (
O-Notation) time-limited Turing machine.
Every t(n)
time-limited Turing machine can be simulated by a register machine with
uniform O(t(n)+n) and
logarithmic O((t(n)+n)log(t(n)+n).
Ok, the same again in plain English:
A Turing machine is basically a theoretical computer imagined for computer science. It has a tape on which letters are stored. It has a program that chooses the action depending on the last read letter. It can write letters and move left and right or not at all. A turing machine has to accept an input and finish in this way, or the algorithm isn't complete (it will run forever)
Turing machines can simulate "Normal" computers and all PC's (they are register machines) can simulate a Turing machine. A non deterministic Turing Machine has some magic knowledge of which route to take. Image a graph or path splitting very often to several directions. A deterministic turing machine would have to check all paths in some form, the non deterministic Turing machines just knows which way to take at each point. And our CS Prof once said: "Polynomial calculation time means it is worth to wait for (the program to complete)"
There are even some non deterministic algorithms today, and you may say that this is far off fantasy when using such "Magic". But i.e. quantum computers can in fact be non-deterministic as they show all possible solutions
as for example a 5 bit quantum computer has 25 results in each step.
The question if P=NP or P!=NP is one of the most important in computer science. If they are equal, a vast number of algorithms can be calculated in polynomial time on standard computers (Algorithms like Clique, BPP, KP, TSP, 3-sat, Partition). Of course these algorithms have to been found first
Definition:
Q is a finite number of states.
Γ (Usually a capital Gamma) is the finite alphabet.
A non deterministic Turing machine NTM is defined like a deterministic Turing machine TM or DTM, only the function that relates the input Letter and the action Q x Γ → Q x Γ x {R,L,N} is replaced by the relation on (Q x Γ) x (Q X Γ x L,R,N}).
For each Language L ∈ NP there is a polynom P and a DTM M, so M will accept the language L in exponential (2p(n)) time.
Whoa.. This looks rather like a
metanode.
Sources (Definitions): "Theroetische Informatik - eine algorithmische Einführung" by Ingo Wegener.
And in fact I study this crap at university.