| |
In computing, it is vital to have some idea of how long a program will take to execute before it is run. If it is going to take the whole of the lifetime of the universe before the computer comes up with the answer to a problem, then it is pointless to tie up valuable hardware to try and solve it. The concept of how long an algorithm will take to solve a given problem is that of complexity. It is usual to take some number obviously connected with the problem (for example, if the problem is to check if n is a prime number, n would be an obvious number to choose) and examine how the length of an algorithm to solve the problem for n varies with n. In the case of the prime, the complexity is n, multiplied by some constant. (It is usual to ignore constants, because the constant is dependent on the particular computer on which the program is run.)
One of the most studied problems in this field is the ‘salesman problem’. Given n towns and a distance, is it possible for a travelling salesman to visit all the towns via some route which has length less than the given distance? This problem is the best-known example of ones which are known as NP-complete; that means that it is not possible to solve the problem in polynomial time (NP stands for ‘no polynomial’) but a solution, a path given as a response, can be checked in polynomial time. SMcL |
|
