2
Trivially every computable problem is reducible to $A_{TM}$. On the other extreme, there are plenty of problems which are $A_{TM}$ "in disguise," which is to say that they are Turing-equivalent to $A_{TM}$ - for example, it's a standard exercise to show that $$\{\langle M\rangle: M\mbox{ halts on input $0$}\}$$ is Turing-equivalent to $A_{TM}$.
A more ...
2
In the context of reducing one language to another, I have only ever seen this referred to using phrases such as "the problem being reduced to", "the target of the reduction", etc. I don't think there is a single word for it—certainly not one that would be universally understood.
1
The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K_k, G \rangle$, which is an instance of graph homomorphism.
However, in general $\langle K_k, G \rangle$ could be much larger than $\langle G,k \rangle$...
1
Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:
\begin{align}
\{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\
&\text{and $M$ }accepts\text{ $w$ after a finite computation}\}
\end{align}
1
If you select two elements from $Z$, then by the pigeonhole principle, there must be a triple that does not contain any element from $Z$, which is impossible.
Only top voted, non community-wiki answers of a minimum length are eligible
