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)|&gt;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)|&gt;0$$
(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| &lt; m ​ and ​ |G2| &lt; 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.