This research focuses on reductions between sets from different complexity classes, such as many-one, Turing, truth- table, and other, as well as considering sets from most basic complexity classes, including probability classes like R and BPP, and sparse sets and tally sets. When are such reductions possible? When they are, how efficient they can be? The ultimate purpose is to make as many connections as possible between different complexity classes, to bring them closer or further apart, depending on the cases. To be more specific, one research direction is to find what consequences can be derived from a given set being reducible to a sparse set, or to a tally set. For example: Is it possible that an NP-complete set is reducible to a sparse set? What are the consequences, using various type of reductions. Is it possible that all BPP sets are reducible to sparse sets? to tally sets? If it is, that would mean that in some way, randomness can be simulated by another type of resources. Can one reduce the problem of building a one-way function to some other complexity class? Can one prove that this reduction must be to a very dense set? How efficiently can one reduce on NP-complete set to another one.
