Complexity of algorithms (extendable essay)

The concept of the complexity of an algorithm is measured as the time or storage space cost required to execute it in the worst or average case. This concept provides a mathematical definition for the rather vague term "hardness," which is sometimes used to characterize algorithms.

When an algorithm is considered from the point of view of complexity, it is assumed that, at its possible inputs , we are given the nonnegative integer function , which is known as the input size, and nonnegative integer time and space cost functions , (space cost is also known as memory storage cost; the cost required for storing the input itself is ignored). The input size is frequently defined as the total number of symbols in the input representation used, but other definitions are also possible. In sorting and search problems, the input size is, as a rule, the number of elements in the input array. In arithmetic problems, the input size can be defined, for example, as the maximum of the absolute values of input integers, the number of digits in the binary representation of this maximum, or the total number of binary digits in all input numbers-the choice depends on the character of the problem under study.

For sorting algorithms, the time cost is fairly completely characterized by the number of comparisons and transfers (assignments or swaps) of elements in the array to be sorted. For arithmetic algorithms, the time cost can be measured as the number of all executed arithmetic operations or, alternatively, by the number of most expensive operations (for example, multiplicative ones: multiplications and divisions), etc.

For a fixed input size, the inputs of an algorithm can vary, in which case the cost generally varies as well. The worst-case time and space complexities of an algorithm are functions of numerical argument defined as

The range of

regarded as an argument of

and

is the range of the size

(the range of

regarded as an argument of

and

is the range of the size

For example, the input of the bubble sort algorithm (which is denoted by Bub) is a numerical array of some length . The number of comparisons required by this algorithm for fixed , ranges from to . Therefore, if is taken as the input size, the complexity of the algorithm is comparisons. The complexity measured as the number of swaps () is equal to the same function of . The space complexity is bounded by a small constant (the original array is replaced by an ordered array).

Relying on the definition of matrix product, we obtain an algorithm for multiplying two square numerical matrices of order . If is taken as the input size, then the time complexity of this algorithm is , multiplications, while the space complexity is (the product is computed in a new place).

An obvious algorithm for testing whether a given integer , is prime, which is referred to as the trial division algorithm, determines whether there is at least one integer between 1 and , that divides . The number of checks whether is divided by one or another integer (for brevity, the "number of divisions") ranges from to (here — denotes the integer part of a number). Denoting this algorithm by TD (from trial divisions) and assuming that the input size is itself, we can say that for any the value of is at most , and there are arbitrarily large , for which this value is equal to . Obviously, the values of are bounded by a small constant.

The worst-case complexity determines a tight upper bound for the possible cost of the algorithm on inputs of given size. It cannot be ruled out that in some cases this bound is rather large, while inputs corresponding to the worst case are rarely encountered among all inputs of given size.

←

Question: Suppose that an algorithm

consists of the sequential (one after another) execution of algorithms

and

, having respective complexities

. Is it true that

←

Question: Let

and

be algorithms. Is it true that

for all

implies

for all possible inputs

←

Question: Is it true that the space complexity of selection sort (with the array length

being the input size) is bounded above by a quantity independent of

←

Question: Let an algorithm

be associated with two, say, time complexities

and

. For example,

and

can be complexities in terms of different operations. Define the complexity

, considering operations of both types. Is it true that

When discussing average-case complexity, we consider only the situation when, for each fixed input size , the corresponding inputs form a finite set . Assume that each is assigned some probability : and . Thus, the time and space cost functions and of an algorithm on inputs of size are random variables on . The average-case time and space complexities of are defined as the expectations of the corresponding random variables:

The execution of any comparison sort is not affected by the values of the elements ; the only important point is their relative order. Therefore, we can assume that the arrays of length , to which sorting algorithms are applied are the permutations of the numbers . For each we can consider the set of permutations of , assigning the probability to each of them. As a result, the average-case complexity of sorting algorithms can be considered. It can be proved that the complexity of the quicksort algorithm QS measured as the number of comparisons satisfies . The average-case complexity of quicksort measured as the number of transfers is at most , where is a small constant. The space complexity is bounded by a constant. (Additionally, a stack of suspended postponed tasks is used, which contains element indices rather than the elements themselves.)

Given an arbitrary algorithm for any probability distribution on the set , the average-case complexity does not exceed the worst-case complexity: , .

For example, with increasing , the worst-case complexity of quicksort measured as the number of comparisons grows as , while the average-case complexity is at most (see the above argument in this section).

If an algorithm is repeatedly applied to inputs of given size, it can be expected that the arithmetic mean of the costs is close to the average-case complexity of this algorithm. However, it is assumed in this case that the inputs of given size are appropriately assigned some probabilities, while this assumption has to be justified (the typical assumption that all the inputs of each size are equiprobable may appear groundless in a particular situation).

S. A. Abramov, Lectures on the Complexity of Algorithms (MTsNMO, Moscow, 2012) (Sections 5-8, Appendix A).

←

Question: Is it true that the average-case complexity of an algorithm requires that a probability distribution be specified:

on the set of all admissible inputs,
on each of the sets of all inputs of fixed size?

←

Question: Let an algorithm

be assigned two average-case time complexities

and

. For example,

and

can be complexities measured as different operations. Let the complexity

, be defined by considering operations of both types. Is it true that

←

Question: Consider the set of all permutations of

, assigning the probability

to each of them. For the permutation

the number of its fixed points is defined as the number of indices

such that

. (In sorting, fixed points do not need to be swapped transfered, which can be used in some forms of sorting.) Is it true that, for a fixed

the expectation of the number of fixed points of the permutation is equal to:

As was discussed above, the worst- and average-case complexities of an algorithm are both a function of a numerical argument-the input size. The growth of the complexity of a particular algorithm with increasing input size is frequently analyzed using asymptotic bounds of the form

The first of them is an upper asymptotic bound, the second is a lower asymptotic bound, and the third combines the first two and can be put in words as follows: “

is on the order of

”, or “

and

are of the same order”.

The first of them is an upper asymptotic bound: according to the following definition known from calculus,

Lower asymptotic bounds can sometimes be useful. The relation holds if and only if there are positive such that for all .

The functions and are of the same order (written as ) if and only if there are positive such that

for all

For example, the relation

implies that

. Additionally, we can show that

and

: a consequence of Stirling's formula is the bound

from which all the above bounds can easily be derived. In the general case, however,

does not imply that

. For example

, but it is not true that

A comparison of the complexities of different algorithms based on their asymptotic complexity bounds can be made not for all types of such bounds. For example, if algorithms and have respective complexities such that , , it cannot be concluded that for all sufficiently large .

A comparison of the complexities of different algorithms based on their asymptotic complexity bounds can be made not for all types of such bounds. In the same manner as, for example, and do not imply that , the relations , do not imply that for all sufficiently large .

A bound of the form (or ) is suitable for "praising" an algorithm , i.e., for characterizing its complexity as rather low, but not for "criticizing" it-for this goal, a bound of the form is more appropriate.

Bounds of the form , , which combine the bounds and , or and , are suitable for characterizing both relatively low and relatively high complexities in corresponding situations.

S. A. Abramov, Lectures on the Complexity of Algorithms (MTsNMO, Moscow, 2012) (Sections 2, 3).

←

Question: Suppose that the polynomial

has a nonzero leading coefficient

. Which of the following assertions is true:

←

Question: Which of the following assertions is not true for the complexity

of the trial division algorithm (see Section 1), which is intended for testing the primality of an integer

(we mean the complexity measured as the number of divisions):

←

Question: Let the cost of any compass-and-straightedge construction in plane geometry be the number of lines (circles or straight lines) drawn in the course of the construction. Consider the problem of constructing a line segment whose length is

of that of the original segment, assuming that

is the input size. Is there an algorithm for solving the problem whose complexity bound is

We can consider different complexities according to the costs taken into account. Suppose that a time cost function gives the number of operations of some type, assuming that they require an identical runtime independent of the operand size and set equal to 1. Then we obtain an algebraic complexity measured as the number of operations of the given type.

As a rule, two time complexities are considered for sorting algorithms: one measuring as the number of comparisons of elements in the array to be sorted and the other measuring the number of element moves transfers. Both are algebraic complexities. Note that they can differ widely in value: among the sorts with a quadratic number of comparisons, the selection sort has an extremely low complexity measured as the number of element moves, namely, this complexity is equal to (worst-case complexities are meant).

The algebraic complexity of arithmetic algorithms measured as the number of multiplications and divisions is called multiplicative complexity. Out of the basic arithmetic operations, multiplication and division are the most expensive ones, and when an arithmetic algorithm is designed considered, it is its multiplicative complexity that is frequently of interest.

In some cases, operations of different kinds are taken into account and the runtime of each of them is set equal to 1. To find each such "mixed" algebraic complexity, the costs for each particular input are taken into account altogether.

Bit time complexity is obtained when the number of bit operations is used as a cost function. In a similar fashion, the space algebraic and bit space complexities can be defined using the number of operations values of the considered type. For example, if two nonnegative integers and , are multiplied, the multiplicative complexity is 1 regardless of the input size. However, for long multiplication with input size - the bit length (the number of digits in the binary representation) of the larger number, the worst-case bit time complexity is .

The complexity of Boolean computations measured as the number of Boolean operations can be treated as algebraic complexity. However, an operation with Boolean quantities is, in fact, a bit operation and, in this sense, the complexity measured as the number of Boolean operations coincides with the bit complexity. Thus, in the Boolean case, the algebraic complexity measured as the number of Boolean operations is the same as that measured as the number of bit operations. The same is true for the space Boolean ( bit) complexity.

←

Question: It is well known that the multiplicative complexity of Gaussian elimination as applied to a system of

linear equations with

unknowns satisfies the bounds estimates

Which of the following assertions is true:

Bound Estimate (3) implies the other two,
Bound Estimate (1) follows from any the other two,
The bound estimate follows from any of 1), 2), 3).

←

Question: Suppose that two positive integers

and

are multiplied using the additions

Let the input size be the maximum of the bit lengths of

and

(denoted by

). Which of the following bounds is true for the complexity of this "supernaive" multiplication:

←

Question: Given a number initially equal to zero, a 1 is added to it at every step until

, is reached. All the additions are performed in columns in the binary system. Is it true that

transfers of 1 to the next position on the left are required in these additions?

The concept of complexity is also considered in the case of randomized algorithms, i.e., algorithms making calls to a random number generator with a known distribution.

The concept of complexity is also considered in the case of randomized algorithms, i.e., algorithms making calls to a random number generator with a known distribution. In the simplest situations, such a generator can be regarded as a function procedure of positive integer argument , that returns one of the elements of the set , so that the value of this function cannot be reliably predicted - any element of the above set can appear with probability .

Generally, the cost of a randomized algorithm is not uniquely determined by its input, but also depends on the generated random numbers. However, the averaged cost for each particular input gives a scalar numeric function on the set of inputs. As a result, the complexity of an algorithm can be treated following the general definition of complexity.

Generally, the cost of a randomized algorithm is not uniquely determined by its input, but also depends on the generated random numbers. In aggregate, the generated random numbers specify a computation scenario. For a fixed input, we can consider the set of all scenarios. Assigning each of them some probability, on the resulting probability space, we can introduce a random variable whose value for a given scenario is equal to the corresponding computational cost. The value of the cost function for a given input can be set equal to the expectation of this random variable (to the averaged cost for the given input). After the cost function is specified and the input size is defined, as usual, we can consider, for example, the worst-case complexity of an algorithm.

[ ]

Another valid approach to randomized algorithms is to assign every possible input a probability space of usual deterministic algorithms. However, each scenario is, in a sense, a deterministic algorithm. The difference between these approaches is terminological.

As was previously discussed, the average-case complexity of a "usual" (deterministic) algorithm is of interest only if correct assumptions are made about the probability of occurrence of one or another input. The considered complexity of randomized algorithms is worst-case complexity but it is determined by the averaged costs. Nevertheless, this averaging can be trusted, since randomized algorithms make use of random number generators in which the probability distribution is fixed and independent of the inputs.

S. A. Abramov, Lectures on the Complexity of Algorithms (MTsNMO, Moscow, 2012) (Section 8).

←

Question: Is it true that the determination of the averaged cost of a randomized algorithm requires specifying a probability distribution:

on the set of all scenarios (see above in this section) assigned to each particular admissible input,
on each of the sets of all inputs of fixed size?

←

Question: An array

is said to contain a majority if more than half of its elements have identical values. Let the operation of verifying whether two elements are equal be defined over the array elements. This operation is called comparison. Given a majority-containing array, the goal is to find an

, such that the value

belongs to the majority of values of

. A possible randomized algorithm for solving this problem is that

is chosen at random (a uniform probability distribution) and it is then verified whether

satisfies the above condition. The number of comparisons required for this verification is

. If

does not satisfy the condition, all steps are repeated. Is it true that the complexity measured as the number of comparisons in this randomized algorithm with

taken as an input size is less than

←

Question: Assume that there is a random number generator returning 0 with probability

or 1 with probability

; moreover, it is only know about

that

and

. This generator can be used to design another one returning 0 or 1 with identical probability

: generating two digits in succession with the help of the original generator, we obtain the combinations 0, 1 and 1, 0 with an identical nonzero probability (the combinations 0, 0 and 1, 1 are ignored). Consider the expected number

of calls to the original random number generator that are required in the construction of a sequence of pairs until 0, 1 or 1, 0 occur. Which of the following assertions is true:

reaches its minimum at ,
reaches its minimum at ,
as the values of decrease monotonically,
is independent of ?

In computational complexity theory, initial assumptions are made about a hypothetical computing device (known as a model of computation).

A random-access machine (RAM) is used as such a model in some cases, while a Turing machine is chosen in other cases.

Sometimes, computations are supposed to be executed by a machine whose memory consists of cells. The total number of cells is assumed to be infinite, which is, of course, a pure abstraction. After writing the result of some computation to a cell or reading the content of some cell, the machine moves on to another cell, etc. It is assumed that the transition from one cell to another does not require any cost. This principle underlies a model of computation known as RAM, i.e., the random-access machine.

In this sense, the RAM differs widely from another well-known model of computation, namely, the Turing machine (TM), in which the time to pass from one cell on the tape to another depends on the distance between the cells.

The former model is closer to actual devices, while the latter is more formalized, which is frequently useful in the existence analysis of an algorithm with certain complexity properties.

We will use the RAM model. The assumption that the size of a cell is unlimited leads to algebraic complexity, while the assumption that one bit is stored in a cell leads to time or space bit complexity.

[ ]

The considered concept of complexity is sometimes referred to as computational complexity (its possible special cases are algebraic and bit complexities) in order to distinguish it from descriptive complexity, which is somehow defined relying on the code of an algorithm.

"Complexity of an Algorithm," Mathematical Encyclopedia (Sovetskaya Entsiklopediya, Moscow, 1977), Vol. 1 [in Russian].

Only computational complexity is discussed below, and we continue to refer to it as complexity.

Considering a class of algorithms for solving a problem yields a family of functions that are complexities (for example, time complexities) of algorithms in this class. Accordingly, we can discuss a lower bound for this family and the existence of a minimal function in it.

Considering a class of algorithms for solving a problem yields a family of functions that are complexities (for example, time complexities) of algorithms in this class.

Consider time complexity in the case where the input size is a nonnegative integer. Let be a fixed class of algorithms for solving some problem. Suppose that the cost of an algorithm and the size of its input have been defined. Let denote the input size. A function is said to be a lower bound for the complexity of algorithms in if the complexity of any satisfies for all admissible input sizes .

A simple example: the function is a lower complexity bound for algorithms of comparison-based search for the least minimal element in a numerical array of length . Indeed, for an array element to be eliminated as inappropriate, it has to be compared at least once and be found larger than its contender. We need to eliminate elements and, in each comparison, precisely one element is larger than another. This means that at least comparisons are required.

[ ]

It is also possible to show that is a lower complexity bound in the worst and average cases for comparison sort algorithms applied to arrays consisting of pairwise distinct numbers (in the average case, all the relative orders of the elements in the original array are assumed to have identical probability ). In the context of the last example, we note that Stirling's formula implies .

If there is a minimal function in this family, then the corresponding algorithm is optimal in the considered class of algorithms.

If there is a minimal function in this family, then the corresponding algorithm is optimal in the considered class of algorithms. If an algorithm such that for some lower complexity bound then is called asymptotically optimal, or optimal in the order of complexity.

[ ]

A trivial algorithm for selecting the least element in a numerical array that requires comparisons is optimal in the class of algorithms for finding the least element in a numerical array of length . All comparison sort algorithms for arrays consisting of pairwise distinct numbers that have complexity measured as the number of comparisons are optimal in the order of complexity, and their complexity is .

is said to be an asymptotic lower bound for the complexity of algorithms in if the complexity of any satisfies . Any lower bound is an asymptotic lower bound as well, but the converse is generally not true. It is easy to show that, if an algorithm is asymptotically optimal in the class , then its complexity is an asymptotic lower bound for the complexity of algorithms in .

←

Question: Is

an asymptotic lower bound for the complexity of algorithms for compass-and-straightedge division of a segment into

equal parts with

regarded as an input size (the cost of any compass-and-straightedge construction in the plane is assumed to be the number of lines (circles or straight lines) drawn in the course of the construction)?

←

Question: Consider the problem of computing

in a set with associative multiplication (i.e., in a semigroup), where

is a given positive integer regarded as an input size. Is

an asymptotic lower bound for the complexity of algorithms for computing

with the help of multiplications?

←

Question: A traveler encounters a wall that extends to infinity in both directions. There is a door in the wall, but neither the distance to it nor the direction toward it is known to the traveler. Let the input size be the number

of steps (unknown to the traveler) that initially separate the traveler from the door. Clearly,

is a lower and an asymptotic lower bound for door-reaching algorithms (in all cases, the traveler has to take

steps). Can a door-reaching algorithm with

complexity bound be proposed?

←

Question: Is it true that the function

is a lower complexity bound for algorithms intended for simultaneously selecting the largest and smallest maximal and minimal elements in an array of length

with the help of comparisons?

←

The correct answer is 2 :
An algorithm can be proposed that requires at most

comparisons. The elements

of the array are searched through in consecutive pairs:

, then

etc. (the last element may remain without a pair). In the

th pair

the smaller and larger elements are compared with the smallest and largest elements found previously among

. If

is odd, then, at the last step,

is compared with the smallest and largest elements found among

. Additionally, the function

is a lower complexity bound for comparison-based algorithms designed for simultaneously selecting the largest and smallest elements in an array of length

I. Pohl. A sorting problem and its complexity. Comm. ACM, V. 15, No 6, 1972, pp. 462 – 466,

S. A. Abramov, Lectures on the Complexity of Algorithms (MTsNMO, Moscow, 2012) (Section 14).

Consequently, the considered algorithm is optimal in the class of all algorithms for solving this problem.

←

Question: Let

be a comparison sort algorithm and

denote the number of elements in the input array. Let

- be the complexities of

measured as the number of comparisons in the worst and average cases, respectively. Which of the following equalities does not hold for any

Optimal algorithms in a given class are not always known. It is also possible that a given class has no optimal algorithm, i.e., an algorithm whose complexity is a lower complexity bound for algorithms in this class. This can be clarified, for example, by the following abstract argument. Suppose that a class consists of only two algorithms, both having a positive integer , as input, which is also its size. Let the complexity of one algorithm be low for even , and high for odd and vice verse for the other algorithm. The arising family of two functions has no minimal one. Accordingly, there is no optimal algorithm in the considered class.

Rather frequently, it is very difficult to answer whether a particular class of algorithms has one whose complexity does not grow too fast with increasing input size.

[ ]

Rather frequently, it is very difficult to answer whether a particular class of algorithms has one whose complexity does not grow too fast with increasing input size. This is especially true when a nontrivial lower complexity bound for algorithms in this class is not available. For example, in the early 1960s, such a question was the existence of an integer multiplication algorithm whose complexity measured as the number of bit operations grows more slowly than , where is the bit length (the number of digits in the binary representation) of the larger of two numbers to be multiplied. In 1962 A.A. Karatsuba found an algorithm of complexity (here, ). In 1963, generalizing Karatsuba's idea and invoking interpolation, A.L. Toom showed that for every there exists a multiplication algorithm of ; complexity. More specifically, for any integer there exists a multiplication algorithm of complexity , where . In 1972 A. Schönhage and V. Strassen used a special form of interpolation - fast Fourier transform - to design an algorithm of complexity . If in this algorithm has the form of , then in the complexity bound can be replaced by . Finally, in 2007 M. Fürer proposed an algorithm of complexity , where is a function growing more slowly than and even more slowly than any iterated logarithm. It is unclear how much this result can be further improved in this direction, in particular, whether a multiplication algorithm of complexity exists.

It should be added that the complexity of Strassen's algorithm (1969) for multiplying two numerical matrices of orderа is , arithmetic operations, while the algorithm following directly from the definition of matrix product has complexity (here, ). Relying on other ideas, in 1987 D. Coppersmith and S. Winograd proposed an algorithm with arithmetic operations, where is the order of the square matrices to be multiplied. In 2012 V. Vassilevska Williams published an algorithm which has O(n^{2.3727}) complexity measured as the number of arithmetic operation. This result has remained the best to this day. Whether for any there is an time algorithm for matrix multiplication remains an open question.

For some classes of algorithms, a difficult question is whether there exists an algorithm in such a class with complexity bounded above by a polynomial whose form is not specified (such an algorithm is known as polynomial-time). If is the size of the input, then an algorithm is polynomial-time if and only if its complexity is for some .

[ ]

For example, there is a polynomial-time primality-testing algorithm with , bit complexity, where the input size is the bit length of the input number; the algorithm was published by M. Agrawal, N. Kayal, and N. Saxena in 2004 and is referred to as AKS algorithm. (For this input size, the complexity of the trivial TD algorithm (see Section 1) measured as the number of divisions (not bit operations) is .)

It is still unknown whether there is a polynomial-time algorithm for decomposing a positive integer into prime factors.

In particular, many unanswered questions concern polynomial-time algorithms for decision problems, i.e., those having a yes/no solution, or a 1/0 solution, etc. In this context, we mention the well-known P≟NP problem.

In particular, many unanswered questions concern polynomial-time algorithms for decision problems, i.e., those having a yes/no solution, or a 1/0 solution, etc.

In this context, we consider the NP class of problems. Any problem in this class can be interpreted as one of verifying the existence of a mathematical object , represented like the original object , by a finite sequence of symbols, i.e., by a string word over some alphabet . The lengths of the strings and are denoted by and . The size of the input is ; the time cost is measured as the number of operations with symbols (by analogy with bit operations). We specify a polynomial and a two-place predicate , defined on strings over . The predicate has the property that, for strings such that , the time required for computing is bounded above by a polynomial in . The corresponding problem in NP is to answer whether it is true that

for given

. (For most problems in NP, it holds that

i.e., the string

is not longer than

For example, let , and nonempty strings be interpreted as binary nonnegative integers. Then the verification of whether a given number is composite can be stated as a problem in NP: here, the predicate (condition) is

“ and is divided by ”,

. The verification of whether

is divided by

takes

time, where

is the bit length of

, i.e., the length of

as a string over the alphabet

Consider the P class of problems. Every problem in this class is to verify whether an input string has a fixed property defined by a predicate such that its value can be computed by a polynomial-time algorithm. It is easy to see that PNP: for example, we can use , .

As was shown above, the primality-testing problem is in NP. Since there exists a polynomial-time algorithm for primality testing (see Section 9), the problem is also in P. However, for some problems in NP, it is not known whether they are in P. Expression defines a one-place predicate . It is not always clear whether there is a polynomial-time algorithm for computing the value of .

An example of a problem that is easily shown to be in NP, but for which it is not clear whether it is also in P is the satisfiability problem: given a Boolean formula written in conjunctive normal form (CNF) with Boolean variables determine whether there is an assignment to the variables that makes the formula evaluate to TRUE.

[ ]

If P=NP were proved, then, in a wide variety of cases, it would easily be shown that a problem is in P (the existence of a polynomial-time algorithm would be established, while the design of such an algorithm is a separate problem), since the fact that a problem is in NP is often relatively easy to show. Informally speaking, P=NP would mean the following: if for any string of the same commensurate length as a given string , we can quickly verify whether and satisfy some fixed conditions, then we can quickly verify whether there is at least one string of the corresponding length that, together with , satisfies these conditions.

However, P=NP has not been proved thus far and experts are inclined to think that it is not true PNP conjecture).

Of course, there is a simple algorithm for checking if () holds for a given : it is possible to search through all strings such that , each time verifying the condition . However, the complexity of this algorithm grows exponentially as .

←

Question: Assume that the cost of any compass-and-straightedge construction in the plane is the number of lines (circles or straight lines) drawn in the course of the construction. Consider the problem of constructing a segment whose length is

of that of the original segment, assuming that

is the input size. Is there a solution algorithm whose complexity grows more slowly than

←

The correct answer is 1 :
Let a segment

be used as a unit one. It is sufficient if we can quickly construct a segment of length

; this operation will be referred to as "the construction of the number

." Then the main problem can be solved by applying the Thales intercept theorem. The following three facts are used here:

(a) The sum and the product of two segments can both be constructed with complexity (the construction of the product is based on the geometric mean theorem, which describes the length of the altitude dropped to the hypotenuse in a right triangle; this theorem is applied twice).

(b) Every positive integer can be written in the factorial number system:

The number

(1) The numbers are sequentially constructed. This requires additions.

(2) The numbers are sequentially constructed. This requires multiplications.

(3) The number is constructed using the numbers obtained. This requires additions and the same number of multiplications.

Overall, the resulting algorithm has

complexity. It was proposed in the paper

M. V. Alekhnovich and A. Ya. Belov, "The complexity of algorithms of constructions by compass and straightedge," Fundam. Prikl. Mat. 7 (2), 597-614 (2001).

←

Question: The existence of a polynomial-time algorithm for decomposing an integer

of bit length

into prime factors remains an open problem, although factorization algorithms are of great importance in cryptography. In this context, consider the following problem: given

, determine whether

has a divisor

such that

. No polynomial-time algorithm (in terms of the bit length of

) is available for this problem. Is it true that, if such an algorithm

were devised, this would automatically produce a polynomial-time factorization algorithm?

←

The correct answer is 1 :
In the presence of such an algorithm

, the prime factors of

can be found via binary search. Assume that it is known that

has no divisors smaller than

, where

, and let

be such that

. We are interested in the smallest prime factor of

lying between

and

. By applying

, where

, the range of the search is roughly halved. Initially, we set

. Applying the algorithm

at most

times yields the smallest prime factor

. Similar computations are performed for

etc. The total number of prime factors of

counting multiplicity, is bounded above by

, and, hence, by

. The bit cost of each division is at most

, where

is a constant. If the bit complexity of

, then the complexity of the prime factorization algorithm described is

, i.e., it is a polynomial-time algorithm.

←

Question: Is it possible to compute the product of two given complex numbers

using several additions and subtractions and only three multiplications of real numbers? (Assume that the values

have been computed; how can a suitable number

be found using a single multiplication so that the computation of the required quantities can be completed using only additions and subtractions?)

←

Question: Is it true that P

NP will be proved if we show that at least one problem in NP is in P?

When we examine the existence of an algorithm of "not very high" complexity, an important role is played by the reducibility of one problem to another. The possibility of quickly solving some problem can imply the same possibility for a number of other problems and, on the contrary, if a certain problem cannot be quickly solved, the same can automatically be implied for a number of other problems.

Considering linear reducibility, we can rigorously define the fact that one computational problem is not harder than another.

Considering linear reducibility, we can rigorously define the fact that one computational problem is not harder than another. Computational problems compared with one another imply transformations of some mathematical objects represented in a similar manner for all the problems to be compared. The input size for algorithms solving these problems also has to be defined in a similar manner. In a comparative study of problems, the cost of executed computations is measured as the number of operations from the same set (for example, arithmetic operations, bit operations, etc.).

Let and be two computational problems. If any algorithm for solving can be put in correspondence with an algorithm for solving such that

then the problem

is said to be linearly reducible to

. Alternatively,

is said to be not harder than

. Here, "linearly" means only that the complexity of

is not, say, the square, cube, etc., of the complexity of

Polynomial reducibility means that, if a computational problem is solvable by a polynomial-time algorithm, then another problem is also solvable by a polynomial-time algorithm.

The polynomial reducibility of a problem to a problem means that, if solvable by a polynomial-time algorithm, then is also solvable by a polynomial-time algorithm. A problem is polynomially reducible to if any algorithm for can be applied to after quick (polynomially bounded in time) transformations of the input. It is easy to show that the polynomial reducibility relation is transitive.

Polynomial reducibility is measured as the concept of an NP-complete problem. All NP-complete problems are in NP (see Section 9) and each of them is remarkable in that any problem in NP is polynomially reducible to it. Thus, if a polynomial-time algorithm were found for at least one NP-complete problem, this would mean that polynomial-time algorithms exist for all problems in NP. Thus, this would mean that P=NP. If a polynomial-time algorithm does not exist for at least one NP-complete problem, then PNP (since any NP-complete problem is in NP).

[ ]

The existence of NP-complete problems was proved independently by S.A. Cook and L.A. Levin. For example, mentioned in Section 9, the satisfiability of a Boolean formula is an NP-complete problem. By showing polynomial reducibility, we can prove the NP-completeness of many other problems, for example, the problem of verifying the existence of a Hamiltonian cycle in a graph, etc.

If an NP-complete problem is reducible to a problem NP, then is also NP-complete, which follows from the transitivity of polynomial reducibility.

←

Question: Is the multiplication of arbitrary square matrices linearly reducible (see above in this section) to the multiplication of upper triangular matrices, assuming that the latter problem is solved only by algorithms for which

(as occurs for all reasonable algorithms designed for this problem)?

←

Question: Are there problems in NP that are not NP-complete?

←

Question: Imagining that there is no polynomial-time algorithm for testing the primality of a positive integer (i.e., the AKS algorithm (see Section 9) does not exist), would it be true that P

NP?

Along with various questions concerning the possible limits for algorithms from one or another class, always important are problems associated with complexity bounds for particular algorithms. Frequently, trivial upper and lower bounds are easy to derive, while deriving close-to-tight bounds for an algorithm requires much effort and nontrivial approaches.

Along with various questions concerning the possible limits for algorithms from one or another class, always important are problems associated with complexity bounds for particular algorithms.

Frequently, trivial upper and lower bounds are easy to derive, while deriving close-to-tight bounds for an algorithm requires much effort and nontrivial approaches. A striking example is given by the Euclidean algorithm. Let be positive integers such that . The search for the greatest common divisor (GCD) of based on the Euclidean algorithm requires the execution of a series of similar steps, each being division with a remainder:

Here,

GCD

. The sequence of obtained remainders decreases (a remainder is less than the corresponding divisor); moreover, all the remainders are nonnegative integers. Therefore, the number of divisions with a remainder is at most

. However, this easy-to-derive upper bound for the number of divisions with a remainder does not reflect the basic advantages of the Euclidean algorithm. It turns out that the number of divisions with a remainder is bounded by the logarithm of

. More specifically, it can be shown that, if

is used as an input size, then the worst-case number of divisions required in the Euclidean algorithm is

. Another surprise presented by this algorithm is associated with its bit complexity. Let the input size be the bit length

(the number of digits in the binary representation) of

. By what was said above, the worst-case number of divisions with a remainder is

. For the naive division of two integers with a remainder, assuming that the bit length of the larger number is

, the bit complexity is on the order of

, which easily yields

for the bit complexity of the Euclidean algorithm. However, a more careful analysis shows that the bit complexity of the Euclidean algorithm is

. Additionally, it can be shown that this complexity cannot be significantly reduced by applying "faster" forms of division: it still satisfies the bound

for any division algorithm of complexity

←

Question: A binary algorithm for finding an element place in an ordered array of length

has complexity

, which implies that the complexity

of binary insertion sort is

. The last term in this sum is the largest, which yields

. Is it true that

←

Question: The complexity

measured as the number of comparisons in binary insertion sort is

. For some values of

elements can be sorted using a smaller number of comparisons. Which is the smallest

of this kind:

←

The correct answer is 3 :
For

this algorithm requires three and five comparisons, respectively. Since

is a lower complexity bound for sorting (see Section 8), the number of comparisons cannot be reduced in this case. However, for

this algorithm requires eight comparisons; moreover, it is possible that five elements are to be sorted, in which case only seven comparisons are required in the worst case. The algorithm can easily be sketched by showing the compared elements by circles joined by an arrow directed from larger to smaller elements. The first element is compared with the second, the third element is compared with the fourth, and the smaller elements found in each case are compared with each other. This requires three comparisons:

Fig. 1. Sorting of five elements: the situation after three comparisons.

As a result, we find the relative order for three elements out of five. Then, the place of the fifth (as yet not compared) element among the ordered three is found by binary search. This requires two comparisons. Thus, one of the two cases depicted in Fig. 2 occurs:

(a) The fifth element is smaller than all the three ordered elements.

(b) The fifth element is larger than the smallest of the three ordered elements.

Fig. 2. Sorting of five elements: the situation after finding the place of the fifth element among the three ordered ones.

In either case, the binary search sort is completed with two comparisons: an insertion is made in the two-element array in Fig. 2a and in the three-element array in Fig. 2b. Overall, seven comparisons are sufficient to solve the problem.

←

Question: Is it true that