Complexity class for some group and graph homomorphism problems

Question

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

Answer 1

(As I mentioned in a comment,) The graph problem is NP-complete, even when H₂ is a triangle.
By putting 3 isolated vertices into H₁, 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}$log₂(|G₁|)$\hspace{-0.02 in}\rceil \hspace{-0.06 in}\cdot \hspace{-0.06 in}\lceil \hspace{-0.02 in}$log₂(|G₂|)$\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$log₂(|G₁|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}\hspace{-0.05 in}+\hspace{-0.06 in}\lceil$log₂(|G₂|)$\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,G₁,G₂$\rangle$ ​ : ​ $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle \hspace{-0.03 in}\in$ S ​ and ​ and ​ |G₁| < m ​ and ​ |G₂| < n
​ ​ ​ ​ and ​ G₁ and G₂ are both 2-groups ​ and ​ $\langle \hspace{-0.02 in}$G₁,G₂$\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))³$\hspace{-0.03 in}\big)\hspace{-0.02 in}$,DTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2^{o(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}$2^{o(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.