# Tag Info

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