Research Initiation: Counting Arguments and the Structure of Complexity Classes

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

In recent years the use of counting arguments has begun to yield results about the structure of complexity classes. Complexity hierarchies have collapsed and new class inclusions have been discovered. This project will use counting arguments to achieve two goals. First, the rival computational paradigms - deterministic, nondeterministic, unique, counting,etc. - will be compared with the goal of discovering new class inclusions and strong (relativized) incomparability results. Second, classes lacking complete languages will be sought. This will add to the tool kit of the field counting based proof techniques that allow easy conversion between various types of non-completeness results.