In most problems of practical interest, the set X is quite large. Branch and bound and dynamic programming methods use the structure of these graphs to solve dop 's without searching X exhaustively. However, the average time complexity of heuristic search algorithms for many problems is polynomial. In these cases, parallel processing can significantly increase the size of solvable problems. For these applications, parallel processing is perhaps the only way to obtain acceptable performance.
Parallel computers having thousands of processing elements are now commercially available.
The cost of these machines is similar to that of large mainframes, but they offer significantly more raw computing power. Due to advances in vlsi technology and economies of scale, the cose of these machines is expected to go down drastically over the next decade. It may soon be possible to construct computers comprising thousands to millions of processing elements at costs ranging from those of high-end workstations to large mainframes. This technology has created substantial interest in exploring the use of parallel processing for search based applications. The workshop featured about twenty invited speakers from Europe and North America.