On the computational complexity of equivalence relations under kernel reductions

Finkelstein, Jeffrey J.
2010

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
Subjects
Department of Computer Science
Permanent URL
http://hdl.handle.net/10427/70356
ID: tufts:UA005.036.006.00001
To Cite: DCA Citation Guide
Usage: Detailed Rights