Vertices are isomorphism classes of objects. How would you characterize edges among all morphisms?

The assumption is that there exists a (in this case, "perfect") hash function which does not have a polynomial-time inverse. This is a standard cryptographic assumption but would fail if, for example, P and NP were equivalent.

It's understandable as you are a new contributor, but you should keep in mind that significantly revising a question multiple times is bad form in mathoverflow, since future readers will not be able to understand old comments/answers. Generally if you find yourself having to revise multiple times that means your question is not ready for mathoverflow, and you need to either figure out what it is you actually want on your own, or find an upstream point of confusion and ask a question about that.

I don't think you can do better than listing the elements. For example suppose your monoid has all self-maps with image {2,...,n} and may or may not have a random map that takes 1 to 1 and {2,...,n} to {2,...,n}, and this map and whether or not it exists is given by inverting a hash which is polynomial time in $|M_n|\cdot n$. Then evidently there is no faster way to determine whether 1 is in your image than inverting the hash.

@EvgenyShinder In fact, the simplest case of LCI subvariety is $X$ itself and I already don't know the answer for this case ($\omega$ is a rational top-degree form, $C$ is open and bounded).

Thanks! Fixed it

If $G$ is any compact noncommutative connected group, this is not true. Indeed, for a compact group you can define an equivariant distance function on $G$ such that $d(a,b) = d(1, ab^{-1}).$ The triangle inequality then implies $$d(X, gXg^{-1}) \le 2 d(1, g).$$ for any element $X\in G.$ But this means that if $a$ is any element in $U$ and $g$ is small enough that the ball around $I$ of radius $2d(1,g)$ is contained in $U$, then $ga^ng^{-1}\in U.$ Thus if $a, b$ are nearby conjugate elements, the conjectured property fails.