P Versus NP Problem - Formal Definitions For P and NP

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:

1. M halts on all input w and
2. 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:

1. For all, such that and ; and
2. the language over is decidable by a Turing machine in polynomial time.

A Turing machine that decides L_R 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.