# Complexity class for some group and graph homomorphism problems

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$$

• The latter is "NP-complete", even when $H_2$ is a triangle. $\;$
– user6973
Commented Nov 15, 2015 at 22:01
• The first one has a quasi-poly time algorithm, by my answer here: cstheory.stackexchange.com/a/33096/129 (the same technique applies). Commented Nov 15, 2015 at 22:11
• 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... Commented Nov 15, 2015 at 22:12

(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
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.

• I dont understand implication of research.microsoft.com/pubs/148550/sl.pdf to Graph Iso problem?
– user34945
Commented Nov 17, 2015 at 16:08
• So deciding if number of graph or group homo is $>0$ is in $P$ while deciding $=0$ is in quasi poly?
– user34945
Commented Nov 17, 2015 at 16:13
• 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). $\:$
– user6973
Commented Nov 17, 2015 at 16:53
• (Hopefully my edit made this clear, but: ​ I'm not claiming that Reingold's result is relevant to Graph Isomorphism.) ​ ​ ​ ​
– user6973
Commented Nov 17, 2015 at 17:10