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
Tufts University. Department of Computer Science.
Permanent URL
ID: tufts:UA005.036.006.00001
To Cite: DCA Citation Guide
Usage: Detailed Rights