On the structure of complete sets

摘要

The many types of resource-bounded reductions that are both an object of study and a research tool in structural complexity theory have given rise to a large variety of completeness notions. A complete set in a complexity class is a manageable object that represents the structure of the entire class. The study of its structure can reveal properties that are general in that the complexity class, and the study of the structure of complete sets in different classes, can reveal secrets about the relation between these classes. Research into all sorts of aspects and properties of complete sets has been and will be a major topic in structural complexity theory. In this expository paper, we review the progress that has been made in recent years on selected topics in the study of complete sets.