chap limits to computation problem ai transform iproblem slntransform sln figure the general process for reduction shown as "blackboxdiagram asymptotically faster (but more complicatedalgorithms are knownbut none is so fast as to be in (nnext we ask the questionis squaring an -digit number as difficult as multiplying two -digit numberswe might hope that something about this special case will allow for faster algorithm than is required by the more general multiplication problem howevera simple reduction proof serves to show that squaring is "as hardas multiplying the key to the reduction is the following formulax xy ( ) ( ) the significance of this formula is that it allows us to convert an arbitrary instance of multiplication to series of operations involving three addition/subtractions (each of which can be done in linear time)two squaringsand division by note that the division by can be done in linear time (simply convert to binaryshift right by two digitsand convert backthis reduction shows that if linear time algorithm for squaring can be foundit can be used to construct linear time algorithm for multiplication