3
$\begingroup$

Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs?

$$\mathsf{Is }|Hom(G_1,G_2)|>0$$

Given two graphs $H_1$ and $H_2$ what is the complexity class in which the following problem belongs (Answered by Ricky Demer in comment)?

$$\mathsf{Is }|Hom(H_1,H_2)|>0$$

$\endgroup$
  • $\begingroup$ The latter is "NP-complete", even when $H_2$ is a triangle. $\;$ $\endgroup$ – user6973 Nov 15 '15 at 22:01
  • 1
    $\begingroup$ The first one has a quasi-poly time algorithm, by my answer here: cstheory.stackexchange.com/a/33096/129 (the same technique applies). $\endgroup$ – Joshua Grochow Nov 15 '15 at 22:11
  • 6
    $\begingroup$ From your recent series of questions I get the impression that you are learning about a subject, but maybe should be reading more and/or thinking more about answering your own questions before asking them here, since the answers are either not hard to figure out or not hard to find via Google or Wikipedia... $\endgroup$ – Joshua Grochow Nov 15 '15 at 22:12
1
$\begingroup$

(As I mentioned in a comment,) The graph problem is NP-complete, even when H2 is a triangle.
By putting 3 isolated vertices into H1, one gets a modified instance such that if the
original instance had no graph homomorphisms then the modified instance also has no
graph homomorphisms else the modified instance has more than 6 graph homomorphisms.

Taking the group problem literally, it is in DTIME(1), since it's decided by the algorithm ACCEPT.


On the other hand, let ∃NZH be the result of instead interpreting the "0" from the
group problem as "the cardinality of the singleton whose element is the zero morphism".

By Reingold's result, ∃NZH is in ​ GC$\hspace{-0.02 in}\big(\hspace{-0.04 in}\lceil \hspace{-0.02 in}$log2(|G1|)$\hspace{-0.02 in}\rceil \hspace{-0.06 in}\cdot \hspace{-0.06 in}\lceil \hspace{-0.02 in}$log2(|G2|)$\hspace{-0.02 in}\rceil$,logspace$\hspace{-0.03 in}\big)$ , ​ since that class
gives the verifier two-way read access to the alleged proof. ​ Furthermore (still using Reingold), logspace machines can compute such non-zero homomorphisms given 2-way read access to
such witnesses. ​ Additionally, by this answer's bound on the number of non-isomorphic groups
(which I don't know how to prove), the negation of ∃NZH is in
GC$\hspace{-0.02 in}\big(\hspace{-0.03 in}\big[\hspace{-0.04 in}\lceil$log2(|G1|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}\hspace{-0.05 in}+\hspace{-0.06 in}\lceil$log2(|G2|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}$ ordinary bits$\hspace{-0.02 in}\big]\hspace{-0.03 in}$+[1 pointer to the advice string]
,logspace$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}n^{O\left(\hspace{-0.02 in}(\hspace{.02 in}\log(n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$.
(The pointer is to where the advice string gives [an ordered pair of reference groups with no non-zero homomorphisms] such that each input group is isomorphic to the corresponding reference group.)

I'm not aware of any evidence for there being $\big[\hspace{-0.02 in}$a set S of ordered pairs $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle$
with min(m,n) not bounded above$\hspace{-0.02 in}\big]$ such that the complement of the language
$\: \big\{\hspace{-0.05 in}\langle \hspace{-0.02 in}$m,n,G1,G2$\rangle$ ​ : ​ $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle \hspace{-0.03 in}\in$ S ​ and ​ and ​ |G1| < m ​ and ​ |G2| < n
​ ​ ​ ​ and ​ G1 and G2 are both 2-groups ​ and ​ $\langle \hspace{-0.02 in}$G1,G2$\rangle \hspace{-0.03 in}\in$ ∃NZH $\hspace{-0.08 in}\big\}$
is in ​ GC$\hspace{-0.03 in}\big(\hspace{-0.03 in}o\hspace{-0.02 in}\big(\hspace{-0.03 in}$(log(m+n))3$\hspace{-0.03 in}\big)\hspace{-0.02 in}$,DTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2o(log(m)$\cdot$log(n))$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$2^$\big(\hspace{-0.04 in}$(m+n)o(1)$\hspace{-0.02 in}\big)$
or in ​ NTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2o(log(m)$\cdot$log(n))$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}n^{o\hspace{-0.02 in}\left(\hspace{-0.02 in}(\hspace{.02 in}\log(m+n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$ ,
where all five little-os are as min(m,n) increases without bound.
However, I certainly suspect that the negation of ∃NZH is already in those two classes,
i.e., without needing to bring S into the picture or assume that the groups are 2-groups.

$\endgroup$
  • $\begingroup$ I dont understand implication of research.microsoft.com/pubs/148550/sl.pdf to Graph Iso problem? $\endgroup$ – user34945 Nov 17 '15 at 16:08
  • $\begingroup$ So deciding if number of graph or group homo is $>0$ is in $P$ while deciding $=0$ is in quasi poly? $\endgroup$ – user34945 Nov 17 '15 at 16:13
  • $\begingroup$ No, for graphs that's NP-hard, and for groups it's extremely easy $\hspace{2.38 in}$ (since there's always the zero homomorphism). $\:$ $\endgroup$ – user6973 Nov 17 '15 at 16:53
  • $\begingroup$ (Hopefully my edit made this clear, but: ​ I'm not claiming that Reingold's result is relevant to Graph Isomorphism.) ​ ​ ​ ​ $\endgroup$ – user6973 Nov 17 '15 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy