Theory of complexity

The theory of complexity studies the intrinsic difficulty formally algorithmic problems .

General information

Presentation

The theory of complexity attempts to know the difficulty (or the complexity) of an answer by Algorithme to a problem arising in a mathematical way. To be able to define it, these three concepts should be presented that are the algorithmic problems, the algorithmic answers to the problems, the complexity of the algorithmic problems.

Algorithmic problem

An algorithmic problem is posed in a mathematical way, i.e. it is rigorously stated in the language of mathematics (best being to use the Calcul of the predicates). These problem comprises assumptions and given and a question. One distinguishes two types of problems:

the problems of decision have a question whose answer is yes or not ,
the problems of existence or search for a solution comprises a question or rather an injunction of the form “to find an element such as…” whose answer consists in providing such an element.

Algorithmic answer

In each category of problems above, one says that a problem has an algorithmic answer if its answer can be is provided by an algorithm. A problem is décidable if it is about a problem of decision, therefore of a problem whose answer is either yes , or not , and if its answer can be provided by an algorithm. Symmetrically, a problem is calculable if it is about a problem of existence and if the calculated element can be provided by an algorithm. The theory of complexity deals only with problems décidables or calculable and seeks to evaluate the resources (time and memory capacity) mobilized to obtain the answer algorithmiquement.

Complexity of an algorithmic problem

The theory of complexity aims knowledge if the answer to a problem can be given very effectively, effectively or on the contrary to be unattainable in practice, with between the two extremes of the intermediate levels of difficulty; for that, it is based on an estimate (theoretical) Time computing and requirements in Computing memory. With an aim of better including/understanding how the problems place the ones compared to the others, the theory of complexity establishes a hierarchy of difficulty between the algorithmic problems, whose levels are called “classes of complexity” . This hierarchy comprises ramifications, according to whether one considers deterministic calculations (the following state of calculation “is determined” by the state running) or not deterministic.

Model of calculation

The analysis of complexity is closely associated with a model of calculation . One of the most used models of calculation is that of the abstract machines in the line of the model suggested by Turing in 1936.

The two models most used in theory of complexity are:

the Machine of Turing
machine RAM (Random access machine)

In these two models of calul, a calculation consists of elementary stages; with each one of these stages, for a given state of the memory of the machine, an elementary action is selected in a whole of possible actions. The deterministic machines are such as each possible action is single, i.e. the action to be carried out is dictated in a single way by the current state of this one. If there can be several choices possible of actions to be carried out, the machine is known as not determinist. It can seem natural to think that the nondeterministic machines of Turing are more powerful than the deterministic machines of Turing, in other words which they can solve in a given time of the problems that the deterministic machines cannot solve in same time.

Other models of calculation which make it possible to study complexity support on the linear Logique (linear Lambda calculation) and the standard S.

Complexity in time and space

One indicates by N the size data. One can take some examples:

the data of a graph with S tops and N edges is of size $\ complement ^2 _s$ : One can for example choose a matric representation (there will be $\ complement ^2 _s$ cells in the matrix to store and each one will be worth 0 or 1).
size of a vector of elements to sorting.

For the deterministic machines, one defines class TIME (T (N)) problems which can be solved in time T (N). I.e. for which there exists at least an algorithm on deterministic machine solving the problem in time T (N) (time being the number of transitions on machine from Turing or the number of operations on machine RAM).

TIME (T (N)) = {L | L can be decided in time T (N) by a deterministic machine}

For the nondeterministic machines, one defines class NTIME (T (N)) problems which can be solved in time T (N).

NTIME (T (N)) = {L | L can be decided in time T (N) by a nondeterministic machine}

Complexity in space evaluates the memory capacity used according to the size of the data; it is defined in a similar way:

SPACE (S (N)) = {L | L can be decided by a deterministic machine by using with more S (N) storage cells}
NSPACE (S (N)) = {L | L can be decided by a nondeterministic machine by using with more S (N) storage cells}

The problem of coding

Problem of decision

Each data-processing problem can be reduced to a problem of decision, i.e. a formulated problem as a question whose answer is Oui or Non , rather than for example the size of the shortest way is 42 . A problem which is not formulated in this manner can be very simply transformed into a problem of decision equivalent. The Problem of the sales representative, which seeks, in a graph, to find once the size of the shortest cycle passing by each top, can be stated in a problem of decision as follows: Exists there a cycle passing one and only once by each top such that the sum of the costs of the arcs used is lower than $B$ , with $B \ in \ mathbb {NR}$ . This problem is equivalent to the problem of the sales representative to the direction where if one can solve one effectively, one can also solve the other effectively.

Classes of complexity

The theory of complexity rests on the definition of classes of complexity which allow to classify the problems according to the Complexité of the algorithms which exist to solve them.

Classify L

A problem of decision which can be solved by a deterministic algorithm spaces of it logarithmic curve compared to the size of the authority is in L.

Classify NL

This class is connected with the preceding one but for a algorithm not determinist.

Classify P

A problem of decision is in P if it can be decided by a deterministic algorithm in a polynomial time compared to the size of the authority. One qualifies the problem of polynomial then.

Let us take for example the problem of the connexity in a graph. Being given a graph to $s$ tops, it is a question of knowing if all the pairs of tops are connected by a way. To solve it, one lays out of the Algorithme of in-depth course which will build a tree covering of the graph starting from a top. If this tree contains all the tops of the graph, then the graph is related. The time necessary to build this tree is with the more $s^2$ , therefore the problem is well in the P. class.

The problems in P correspond in fact to all the easily soluble problems.

Classify NP

A problem NP is NR one-determinist P olynomial (and not Non polynomial , very current error).

The class NP joins together the problems of decision for which the answer yes can be decided by a nondeterministic algorithm in a polynomial time compared to the size of the authority.

In an equivalent way, it is the class of the problems which admit an algorithm in P which, being given a solution of the problem NP (a certificate ), is able to answer yes or not .

Intuitively, the problems in NP are all the problems which can be solved by enumerating the whole of the possible solutions and by testing them with a polynomial algorithm.

For example, the search for Hamiltonian cycle in a graph can be done with two algorithms:

the first generates the whole of the cycles (what is exponential);
the second tests the solutions (in polynomial time).

Classify Co-NP (Complementary to NP)

It is the name sometimes given for the equivalent of the class NP , but with the answer not .

Classify PSPACE

It gathers the problems décidables by a deterministic algorithm in polynomial space compared to the size of its authority.

Classify NSPACE or NPSPACE

It joins together the problems décidables by a nondeterministic algorithm in polynomial space compared to the size of its authority.

Classify LOGSPACE

Classify EXPTIME

It gathers the problems décidables by a deterministic algorithm in exponential time compared to the size of its authority.

Properties

There are inclusions:

P $\ subset$ NP , and symmetrically P $\ subset$ Co-NP
NP $\ subset$ PSPACE = NPSPACE , and Co-NP $\ subset$ PSPACE .

Indeed, a polynomial problem can be solved by generating a solution and by testing it with a polynomial algorithm. Any problem in P is also in NP.

Research actively works to determine if NP $\ subset$ P (conclusive with P = NP ) or if, on the contrary P $\ ne$ NP (see the open problem P = NP).

C-complete problem

That is to say C a class of complexity (like P , NP , etc). It is said that a problem is C-complete if

it is in C , and
it is C-difficult (one uses sometimes the incorrect translation C-hard ).

A problem is C-difficult if this problem is at least as hard as all the problems in C . Formally one defines a concept of reduction: Are $\ Pi$ and $\ Pi'$ two problems; A reduction of $\ Pi'$ with $\ Pi$ is an algorithm transforming any authority of $\ Pi'$ into an authority of $\ Pi$ . Thus, if there is an algorithm to solve $\ Pi$ , one can also solve $\ Pi'$ . $\ Pi$ is thus at least as difficult to solve as $\ Pi'$ .

$\ Pi$ is then C-difficult so for any problem $\ Pi'$ of C , $\ Pi'$ is reduced to $\ Pi$ . When one speaks about Np-difficult problems one is authorized only reductions in P, i.e. the algorithm which calculates the passage of an authority of $\ Pi'$ with an authority of $\ Pi$ is polynomial (see polynomial Réduction). When one speaks about P-difficult problems one is authorized only reductions in LOGSPACE.

Reduction of problems

To show that a problem $\ Pi$ is C - difficult for a given class C , there are two ways of proceeding: to show that any problem of C is reduced to $\ Pi$ , or it is enough to show that a problem C - difficult is reduced to $\ Pi$ . It is this second method, easier, which is used as soon as one has at least a problem C - complete.

Transformation of problem

The simplest reduction (it is not besides really a reduction) simply consists in transforming the problem to be classified in a problem already classified.

For example, let us show here that the problem of the search for Hamiltonian cycle in a directed graph is Np-Complete.

the problem is in NP : One can find way obvious an algorithm to solve it with a nondeterministic machine, for example by stating all the cycles then while selecting shortest.
We have the problem of the search for Hamiltonian cycle for the not directed graphs. A graph not directed can be transformed into a graph directed in “doubling” each edge so as to obtain, for each pair of adjacent nodes, of the ways in the two directions. It is thus possible to bring back the problem known, Np-difficult, with the problem which we want to classify. the new problem is thus Np-difficult .

The problem being in Np-difficult NP and , it is Np-complete .

Polynomial reduction

See the complete article polynomial Reduction .

Theorem of Cook

The problems are classified in an incremental way, the class of a new problem being deduced from the class of an old problem.

The establishment of “a first” Np-complete problem to classify all the others however proved to be necessary: Thus the Theorem of Cook (of Stephen Cook) class the Np-Complete Problem SAT like .

Np-Complete problem

The most studied complete problems are the Np-complete problems. The class of complexity being per definition reserved for problems of decisions, one will speak about Np-difficult problem for the problems of optimization knowing that - for these problems of optimization - one can easily build a problem which is associated and is for him in NP and which is thus Np-complete.

In an intuitive way, to say that a problem can be decided using a polynomial nondeterministic algorithm means that it is easy, for a given solution, to check in a polynomial time if this one answers the problem for a given authority (using a certificate); but that the number of solutions to test to solve the problem is exponential compared to the size of the authority.

The not-determinism makes it possible to mask the exponential size of the solutions to be tested while making it possible the algorithm to remain polynomial.

; Problem Np-Complete famous:

Problem SAT and alternative 3SAT (but 2SAT is polynomial); let us note that there exist software (known as SAT solvers ) specialized in the powerful resolution of problems SAT;
Problème of the sales representative
Problème of the Hamiltonian cycle
Problème of the clicks maximum
Problèmes of colorings of graphs
overall Problème dominating in a graph
Problème of cover of tops in a graph

Although less studied, the complete problems for the other classes are not less interesting

the Reach problem (or Accessibility) which consists in knowing if there exists a way between two tops of a graph is NL-complete
the problem Circuit Been worth (and monotonous Circuit Been worth: the same one but without negation) are P-complete problems
the Problème QBF (SAT with quantifiers) is PSPACE-complete

Note: all the problems of the class L are L-complete considering the concept of reduction is too vague. Indeed the function which must transform an authority from one problem to another must be calculated in space logarithmic curve.

Lists

21 Np-complete problems of Karp
List of Np-complete problems

The open problem PNP

There is trivialement $\ mbox {P} \ subseteq \ mbox {NP}$ because a deterministic algorithm is an algorithm nondeterministic private individual, which, known as in simpler words, means that if solution can be calculated in polynomial time, then it can be checked in polynomial time. On the other hand, the reciprocal one: $\ mbox {NP} \ subseteq \ mbox {P}$ , which is the true difficulty of the equality $\ mbox {P} = \ mbox {NP}$ is one of the most fundamental and interesting problems open in data-processing theoretical. It was posed in 1970 independently by Stephen Cook and Leonid Levin. The majority of the specialists conjecture that the Np-complete problems are not soluble in a polynomial time. Starting from there several approaches were tried:

Of the Algorithmes of approximation makes it possible to find solutions approximate of the optimum in a reasonable time for a certain number of programs. In the case of a problem of optimization one generally finds an answer correct, without knowing if it is about the best solution;
Of the stochastic Algorithms: by using random random numbers one can “force” an algorithm not to use the least favorable cases, the user having to specify an allowed maximum probability that the algorithm provides an erroneous result. Let us quote in particular like application of the algorithms of Test of primality in polynomial time in the size of the number to test. It should be noted that a nonstochastic polynomial algorithm was proposed for this problem in August 2002 by Agrawal, Kayal and Saxena;
Of the Heuristique S makes it possible to obtain generally good but nonexact solutions in a moderate computing time;
Of the algorithms by Separation and evaluation make it possible to find the solutions exact. The computing time is of course not limited polynomialement but, for certain classes of problems, there can remain moderate for relatively large authorities;
One can restrict the class of the problems of entry to a subclass sufficient, but easier to solve.

Models of calculation

These theorems were established thanks to the model of the machines of Turing. But of other models are used in complexity, of which:

the recursive functions due to Kleene
the cellular automats
machines with registers (RAM)
the Lambda-calculation

It is known that all these models are equivalent: all that a model makes it possible to calculate is calculable by another model. Moreover, thanks to the multipurpose machines of Turing, one knows that all that is intuitively calculable is modélisable in these systems. The consequences are important and numerous. The first fact that this article is readable: one can build computers. This established a link with the Theory of the calculability.

Notes and references of the article

Random links: