NP

(computational complexity:)

The class of all languages which can be recognised by a nondeterminstic Turing machine (which see!) in polynomial running time. Clearly this class includes all problems in P. It seems very clear that it should contain problems which are not in P, but unfortunately this is not known (and is very much an open problem). Symbolically, we know that

P ⊆ NP ;

the question is if

P = NP .

Briefly put (but you should still read the node!), a "nondeterministic" Turing machine is a Turing machine with an extra tape. The extra tape is initially filled with arbitrary bits. The machine "accepts" a word w if there is some initial configuration of the arbitrary bits on the extra tape for which the machine halts with output "1" on its main tape. Note that we have no known source which will supply us with these arbitrary bits!

Since a Turing machine running in polynomial time will require the use of only polynomially many nondeterministic bits, we can prespecify the "correct" bits for a successful computation for any element of a language in NP. So an alternative definition of NP is the set of all languages L for which a function f(x,y) exists, which is in P, and such that x is in L iff there exists a y, with |y| polynomial in |x|, for which f(x,y)=1.

Many complete problems are known for NP. Among them are SAT, 3-SAT, hamiltonian path, chromatic number, and integer linear programming. See NP-complete for further discussion of this "tip" of the NP iceberg.

---

Note on a misconception appearing below:

It is NOT true to say that the class NP consists of all problem solvable in exponential time on a deterministic Turing machine. While it is true that

NP ⊆ ∪_c≥1 DTIME(2^nc)

i.e., any problem in NP can be solved in exponential time, the converse is not known to be true! (Sketch of a proof why the inclusion holds: Run the NDTM on every possible initial configuration of arbitrary bits; accept if even one initial configuration finds a solution. If the machine runs in time O(n^c), this requires us to scan O(2^nc) different configurations for total deterministic running time O(n^c⋅2^nc) = O(2^nc)). Note also that "exponential time" actually means more than just time O(2ⁿ); this is another one of the oddities of notation in computational complexity.

Similarly, there are other "magic" ways to use arbitrary bits which yield different complexity classes. co-NP is one example. A more interesting example is the problem of solving all games of perfect information and polynomial length for which legal moves and victory can be determined in polynomial time. This problem is not known to be in NP; however it is a complete problem for PTIME, and can be solved in not much more than "exponential" time.

Online abbreviation for "No problem" as an alternative to You're welcome. I've mostly seen it during my brief foray into Everquest, but I imagine it's widespread in the onlime gamers subculture and elsewhere.

I find it interesting in that it brings the English polite response to Thank you in line with most other languages' response. Most languages have a "No problem" or "It's nothing" way to answer. Of course, I imagine it's used for economy - the less typing, the more time for gaming.

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 2⁵ 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 (2^p(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.

NP in linguistics means noun phrase. The basic structure of a sentence may be symbolized in the phrase structure rule S -> NP VP, where VP is the verb phrase (sometimes called predicate). An NP may contain other NPs, e.g. "The Man Who Mistook His Wife for a Hat" is an NP (it can be used wherever "the man" is) containing a relative clause, which is itself a sentence with three NPs: subject "who", object "his wife", and "a hat" within the prepositional phrase "for a hat". Likewise "The Man with the Golden Gun" is an NP containing a subordinate NP "the golden gun". It need not contain a noun, but may be a pronoun instead, since this functions the same way in the syntax.

Np is the symbol for the element neptunium.

Also, Np is the symbol for the neper, a newly-invented (1998) SI unit for logarithmic quantities. A neper (named after John Neper or Napier) is dimensionally equal to one, and is such that e.g. 43 Np is e times larger than 42 Np.

NP or N.P. = (1) New Providence, (2) Notary Public.

n.p. or N.P. = "no place", referring to title pages of books, as n.d. for "no date".

np or n.p. = naya paisa, plural naye paise, formerly the 100th part of a rupee.

.np is the Internet top level domain for Nepal.

A lot of the time, doubling the speed of your computer will double the amount of data it can process over a given time interval. For instance, if you have a computer that can crunch through 500 computations of a certain type in ten seconds, and you double the speed of that computer, it should be able to crunch through 1000 computations of the same type in ten seconds.

Sadly, this is not always true. For NP problems that do not have a known polynomial solution, doubling the speed of the computer will only add a fixed amount of computations.

For example, suppose our 100 MHz machine can process 500 units of data in 10 seconds. The 200 MHz machine will not necessarily be able to handle 1000 units. It may only be able to handle 550. To be able to handle 600, we would need a 400 MHz machine and so on.

Units   Speed
500     100 MHz
550     200 MHz
600     400 MHz
650     800 MHz
700     1.6 GHz
750     3.2 GHz
800     6.4 GHz

As you might see, solving a signifigantly large problem (one million units for instance) is going require a computer faster than the combined speeds of all computers in existence.

If P were equal to NP (Though unlikely) that would mean that there does in fact exist some algorithm which would be able to handle the problem in polynomial time.

I've added this node to include various little notes about NP that seem to missing from the other nodes in this section:

• Assuming P != NP (and it this point it looks unlikely), NP complete problems are all problems that take exponential time to solve with determininistic hardware. While there are a whole series of problems defined which have this property (SAT, traveling salesmen, etc), the basic fact remain that current Computer Science/mathimatical theory cannot yet pinpoint the fundemental feature of these problems that makes them hard. This may be the missing piece of the puzzle in explaining why we are unable to prove that the set NP is not equal to the set P.
• Another way to thinking of the nondeterministic machines described in this node (instead of thinking of them as "magical") is to say that no matter what the algorithm or input, they can check ALL solutions at the same time.