Logic and computational complexity

点击翻译按钮获取中文摘要

The main aim of the research is to understand why certain problems are difficult to solve using computers.  Typical of such problems are those in which a certain number of simple constraints must be satisfied, as in constructing schedules.  The characteristic feature of such problems (known by the technical name of NP-complete problems), is that a solution, if found, is easy to check, but deciding whether or not such a solution exists in the worst case requires an exponentially long time relative to the size of the input.   The principal aim of the theory of complexity theory is to decide whether or not such problems, that seem to require exponentially long computation times in the worst case, really do require such times. My own research aims to work towards showing that exponentially long times are in fact required in the worst case by proving lower bounds on the length of certain kinds of proofs.  Since a computation showing that a solution doesn't exist can be considered as a proof of a kind, lower bounds on the length of proofs show that certain kinds of algorithms (including the algorithms most often used in practice to solve such problems) cannot be efficient in the worst case.