On the computational complexity of equivalence relations under kernel reductions

Finkelstein, Jeffrey J.

In this paper we analyze the notion of kernel reductions among equivalence problems, as defined in Fortnow and Grochow. We first examine what kernel reductions look like, practically, among feasible equivalence problems. We next provide some evidence that the restriction of a polynomial time kernel reduction is not on the time complexity of the reduction, but on the number of equivalence classes i... read more

This object is in collection:
Undergraduate honors theses
Department of Computer Science
Permanent URL
ID: tufts:UA005.036.006.00001
To Cite: DCA Citation Guide
Usage: Detailed Rights