Variables versus Size: Tradeoffs in Descriptive Complexity

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

This project will develop a prototype system whose ultimate goal is to automatically determine the complexity of a given combinatorial problem. Many researchers have observed that naturally occurring problems tend to be complete for one of a small handful of important complexity classes. Furthermore, they are complete for these classes via the weakest imaginable reductions, namely quantifier-free projections (qfps). It was shown by the investigator and his coauthors that problems complete for the same class via qfps are isomorphic. What this means is that although there is an arbitrarily rich class of different computational problems, in practice we often encounter problems that look different, but are essentially one of a handful of fundamental complete problems. Now that SAT solvers have become so fast, this project will show that it is feasible to use them to check whether or not (small) qfps exists between all (small) instances of a given pair of computational problems. In this way, we will often be able to automatically check whether reductions exist and thus determine the complexity of a given computational problem. This research will add to our understanding of the fundamental complexity of problems. In the longer term, it will lead to improved algorithms that automatically derive efficient data structures and algorithms for given computational problems.