Everyday Computational Challenges that Elude Computers

Throughout the sciences, engineering and the world of commerce, computational problems arise that have the character of puzzles. Like the Sudoku puzzle, such combinatorial search problems involve finding patterns or arrangements that satisfy a desired property. Examples include scheduling classes at a school or jobs at a factory, finding the best route for a traveling salesman, designing a computer chip, folding a protein, packing objects into bins, or fairly dividing the assets of an estate. Typically, in such problems, it is easy to check whether any given arrangement satisfies the property, but the number of possible arrangements is astronomical, so that the "brute force" method of listing and checking all the arrangements, would be intractable. A central open question, called the P vs. NP problem, is whether there exist combinatorial search problems for which no efficient "short cut" solution method exists, so that intractability is unavoidable. The question can be restated as follows: is there a combinatorial search problem for which checking the validity of a given arrangement is easy, but finding a valid arrangement is intractable? It has been shown that, if even one such intractable problem exists, then a huge number of combinatorial search problems, including all those listed above, as well as most of the combinatorial search problems that arise in practice, are intractable. The existence of intractable combinatorial search problems would be bad news for the world of computation, but good news for e-commerce, which depends on the intractability of the problem of breaking certain data encryption methods.

This lecture is one of over 300 events on campus during Cal Day, a once-a-year opportunity for one and all to experience the stimulating, energetic and multifaceted life of UC Berkeley. Learn more about Cal Day here.