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:
“Good gentlemen, look fresh and merrily.
Let not our looks put on our purposes,
But bear it as our Roman actors do,
With untired spirits and formal constancy.”
—William Shakespeare (1564–1616)
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)