| Description |
-
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 ... read morein the equivalence relations being reduced. We then examine the graph isomorphism problem and problems equivalent to it under polynomial time many-one reductions, and find that of these problems the ones which are equivalence problems are in fact equivalent to the graph isomorphism problem under polynomial time kernel reductions.read less
|
|---|
This object is in collection
