The inherent complexity of various computational problems will be investigated, in the hope that a deeper understanding may be gained as to why certain problems seem to require a nontrivial amount of computing resources for their solution. Complementary to this effort, the expected performance of a number of existing algorithms will also be studied. The principal mathematical tools needed for this research are likely to be combinatorial and probabilistic techniques. To delineate the scope of this investigation, representative problems are given from Boolean circuits, decision trees, data structures, geometric computations, and the mathematical analysis of algorithms.
