Formal Definitions For P and NP
Conceptually a decision problem is a problem that takes as input some string w over an alphabet, and outputs "yes" or "no". If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) that can produce the correct answer for any input string of length n in at most steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is defined as the set of all languages that can be decided by a deterministic polynomial-time Turing machine. That is,
where
and a deterministic polynomial-time Turing machine is a deterministic Turing machine M that satisfies the following two conditions:
- M halts on all input w and
- there exists such that (where O refers to the big O notation),
-
- where
- and
NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach to define NP is to use the concept of certificate and verifier. Formally, NP is defined as the set of languages over a finite alphabet that have a verifier that runs in polynomial time, where the notion of "verifier" is defined as follows.
Let L be a language over a finite alphabet, .
L ∈ NP if, and only if, there exists a binary relation and a positive integer k such that the following two conditions are satisfied:
- For all, such that and ; and
- the language over is decidable by a Turing machine in polynomial time.
A Turing machine that decides LR is called a verifier for L and a y such that is called a certificate of membership of x in L.
In general, a verifier does not have to be polynomial-time. However, for L to be in NP, there must be a verifier that runs in polynomial time.
Read more about this topic: P Versus NP Problem
Famous quotes containing the words formal and/or definitions:
“The spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (1869–1950)
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)