VRP Variants

P and NP Class Problems

P Problems

Informally, the class P is the class of decision problems solvable by some algorithm within a number of steps bounded by a fixed polynomial in the length of the input.

To define the class precisely it is necessary to give a formal model of a computer. The standard model in computability theory is the Turing machine, introduced by Alan Turing in 1936 [Turing 36]. Although the model predates physical computers, it is still accepted as the proper model for defining the notion of a computable function.

Formally, the elements of the class P are languages. We define the class P of languages as:

$P = {L | L = L(M)}$ for some Turing machine $M$ running in polynomial time,

where:

L is a subset of $Σ*$ , the set of finite strings over $Σ$ , a finite alphabet with at least two elements.
M is a Turing machine with an associated input alphabet $Σ$ .
L(M) is the language accepted by M. It is defined by $L(M) = {w ∈ Σ* | M accepts w}$ : M accepts w (a string in $Σ*$ ) if its computation terminates in the accepting state.

NP Problems

NP does not mean "non-P". The notation stands for nondeterministic polynomial time, since NP was originally defined in terms of nondeterministic machines — machines that have more than one possible move from a given configuration.

A problem belongs to the NP class if it is solvable in polynomial time by a nondeterministic Turing machine (a "parallel" machine that can take many computational paths simultaneously, with the restriction that the parallel computations cannot communicate). Equivalently, a problem is in NP if a proposed solution can always be verified in polynomial time.

Every P problem (whose solution time is bounded by a polynomial) is also in NP. If P and NP are not equivalent — the famous open P ≠ NP question — then solving NP problems requires, in the worst case, an exhaustive search.

NP-Hard Problems

A problem is NP-hard (nondeterministic polynomial-time hard) if solving it in polynomial time would make it possible to solve all problems in class NP in polynomial time. That is, a problem is NP-hard if an algorithm for solving it can be translated into one for solving any other NP problem. NP-hard therefore means "at least as hard as any NP problem". The Vehicle Routing Problem is NP-hard.

NP-Complete Problems

A decision problem C is NP-complete if it is in NP and if every other problem in NP is reducible to it [Cook 1971]. "Reducible" means that for every NP problem L there is a polynomial-time algorithm that transforms instances of L into instances of C with the same truth values. Consequently, a polynomial-time algorithm for C would solve all NP problems in polynomial time. Deciding whether a graph has a Hamiltonian cycle is a classical NP-complete problem.