Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem?
In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards derandomization of Polynomial Identity Testing?
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ Can you explain why you suspect there is a relation between them? $\endgroup$– KavehCommented Dec 8, 2015 at 0:33
-
1$\begingroup$ my suspicion comes from drops.dagstuhl.de/opus/volltexte/2011/3320/pdf/2.pdf and also it seems one could cook up graph structures with closed paths corresponding to monomials or monomials with linear transformation of variables. $\endgroup$– TurboCommented Dec 8, 2015 at 1:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
The paper you linked in the comments - and references therein - already seems to answer your first question.
For your second question: I have little reason to think that there is a theorem of the form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq and RingIso are relatively close to one another, and RingIso is as hard as integer factoring...)
Note that equivalence problems in general tend to be nontrivially harder than their specific instances or testing for triviality. For example, Formula Isomorphism is believed to be intermediate between the first two levels of $\mathsf{PH}$, although testing isomorphism to the trivial formula is $\mathsf{coNP}$-complete. (This is the Boolean analogue of your suggestion of trying to use PolyEq to solve PIT. Of course, one could argue that our intuition for the intermediate status of Formula Iso is largely based on Graph Iso...) As another example, testing for Knottedness is in $\mathsf{NP} \cap \mathsf{coNP}$ (assuming GRH; albeit only recently), but the current best upper bound on testing Knot Equivalence is that it can be done in time that is a tower of 2's of height $c^n$, where $n$ is the number of crossings and $c = 10^{10^6}$ (see here). Although it is possible that both Knottedness and Knot Equivalence are in $\mathsf{P}$, the latter seems significantly harder than the former.
answered Dec 8, 2015 at 5:08
-
$\begingroup$ Thank you for the detailed post. Is there a matrix theoretic framework for Knot equivalence analogous to $A=PBP'$ ($A,B$ adjacency matrices of isomorphic graphs with $P$ permutation) framework for graph equivalence? $\endgroup$– TurboCommented Dec 8, 2015 at 5:32
-
$\begingroup$ Not as far as I know, at least not with reasonably-sized matrices. Note that if A is $N \times N$, then most natural problems of the form you describe can be decided in $2^{O(N^2)}$ time using quantifier elimination over $\mathbb{R}$, which is much better than the current best upper bound for KnotEq (unless $N$ itself is gigantic). $\endgroup$ Commented Dec 8, 2015 at 5:57
-
$\begingroup$ Does representation matrix need to be polynomial sized? How else could we feed input to problem (like any other decision problem)? $\endgroup$– TurboCommented Dec 8, 2015 at 6:06
-
$\begingroup$ I am trying to find details here but I am unable to math.hmc.edu/seniorthesis/archives/2006/jmay/… $\endgroup$– TurboCommented Dec 8, 2015 at 6:12
-
1$\begingroup$ @Turbo: One way is by a 4-valent graph with each vertex endowed with the data of over-and-under crossings (the knot diagram). However, note that equivalence between knots with this input format isn't phrased in the way you describe, for example because two knots with different numbers of crossings can be equivalent. (Alternately, you can represent a knot by a piecewise-linear knot with rational - or even integer, I think - coordinates in Euclidean 3-space.) $\endgroup$ Commented Aug 8, 2016 at 5:40