An Invitation to the Dance It is an underappreciated fact that sets may
have various types of complex- ity, and not all types are in harmony
with each other. The primary goal of this book is to unify and make more
widely accessible a vibrant stream of research-the theory of
semi-feasible computation-that perfectly showcases the richness of, and
contrasts between, the central types of complexity. The semi-feasible
sets, which are most commonly referred to as the P- selective sets, are
those sets L for which there is a deterministic polynornial- time
algorithm that, when given as input any two strings of which at least
one belongs to L, will output one of them that is in L. The reason we
saythat the semi-feasible sets showcase the contrasts among types of
complexity is that it is well-known that many semi-feasible sets have no
recursive algorithms (thus their time complexitycannot be upper-bounded
by standard time-complexity classes), yet all semi-feasible sets are
simple in a wide range of other natural senses. In particular, the
semi-feasible sets have small circuits, they are in the extended low
hierarchy, and they cannot be NP-complete unless P = NP. The
semi-feasible sets are fascinating for many reasons. First, as men-
tioned above, they showcase the fact that mere deterministic time
complex- ity is not the only potential type of complexity in the world
of computation.