IntroductionThe following is an extract from the explanatory notes for the draft Digital Technology achievement standard 2.44 (Feb. 2011 version) - Demonstrate understanding of advanced concepts from computer science. It is included as it sums up quite well what complexity and tractability are. I have underlined parts that I think are important.
The complexity of a problem...is a measure of the most efficient way of computing a solution to the problem. There are usually many different ways of computing a solution; it is only the most efficient ways that determine the complexity of the problem.
A tractable problem is one whose solution can be computed in a feasible amount of time, even for large inputs. An intractable problem is one whose solution can be computed in a feasible amount of time only for small inputs, and rapidly becomes infeasible as the size of the input grows larger. The complexity of a problem is measured in the amount of time it takes for an efficiently constructed program modeling it to run. If it takes too long or takes too many resources (e.g. memory) it is said to be intractable. A good analogy used by Dr Tim Bell of Canterbury University is: "Complexity is the time taken; tractability is a rule for deciding if the time is too long. Kind of like the difference between the speed of your car, and the speed limit." The following link points to a page that has some additional useful information: computing students - program complexity A problem is tractable if an algorithm can be constructed to solve it, and a computer program based on this algorithm runs to completion in a reasonable amount of time using a reasonable amount of resources. Again frrom the explanatory notes to the draft standard.
An example of an intractable problem is listing all the possible patterns that can be made with n bits (eg, a sequence of black or white squares). While this is easy for 10 bits (210 = 1024 patterns), feasible for 20 bits (220 = 1048576 patterns), it would be infeasible for 100 bits (1267650600228229401496703205376 patterns).
Finding the prime factors of an n-digit number is also believed to be infeasible, and is the basis for the security of the most important public key cryptography system – if we had an efficient algorithm for doing this (ie, if the problem were tractable), then it would be feasible to crack the codes, which would probably bring eCommerce to a halt. Finding the optimal layout of containers in a container port is an intractable problem, so that programs to plan container placement can only use imperfect, though good enough, approaches to get reasonably good layouts. Another problem that can become intractable when it is scaled up is the route a courier driver takes when delivering their packages. Which is the most efficient route in terms of time and distance covered between drop-offs? Where do they go first, then second, then third...? Should traffic conditions be taken into account? For instance, the shortest route from a choice of two may take longer to travel because of greater traffic congestion (which may change by the hour). As you can see, there are many different variables to take into account. This adds to the complexity of any computer program designed to solve the problem (or give the best solution). This problem is of the Traveling Salesman variety discussed on the Intractable Problems page. |