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 Corporate name Temporal Permanent URL
To Cite:
DCA Citation Guide    EndNote
Detailed Rights