# prove that there is a complete language in $L \cup \{A_{TM}\}$

$$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$$

$$L$$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space

Given the language $$L \cup \{A_{TM}\}$$,

we will say that $$A$$ is complete in $$L \cup \{A_{TM}\}$$ if:

• $$A \in L\cup\{A_{TM}\}$$
• For every $$B\in L \cup \{A_{TM}\} \implies B\le_LA$$

Is there a complete language in $$L \cup \{A_{TM}\}$$?

• What is $L$? What is $A_{TM}$? – dkaeae Jul 9 at 14:15
• @dkaeae Please see my edit – ItayItay Jul 9 at 14:30
• Which langauge do you think would be a good candidate to be complete in this class? How would you go about proving it? – Shaull Jul 9 at 14:36
• Does $A_{TM}$ reduce to any logspace language? Does it reduce it itself? Basically, the first thing that you might guess would be the answer is the answer. – David Richerby Jul 9 at 14:38
• Observe that $L\cup \{A_{TM}\}$ is not a language, it is a class of languages. Try using $A_{TM}$ as a candidate. – Shaull Jul 9 at 14:52

We will show that $$A_{TM}$$ is complete for your class.
In order to show that, we need to show that for every language $$A\in L\cup \{A_{TM}\}$$, it holds that $$A\le_L A_{TM}$$.
First, if $$A=A_{TM}$$, then the trivial reduction suffices. That is, a reduction that given input $$x$$, return $$x$$. Clearly $$x\in A_{TM}\iff x\in A_{TM}$$.
Now, if $$A\in L$$, we need to work slightly harder. We need to show that $$A\le_L A_{TM}$$. In order to do that, we construct a reduction from $$A$$ to $$A_{TM}$$, as follows: let $$M$$ be a deterministic TM that decides $$A$$ in logspace (why does there exist such a machine?).
Now, the reduction works as follows: given input $$x$$, the reduction uses $$M$$ to check whether $$x\in A$$. If $$x\in A$$, the reduction outputs $$\langle\epsilon, T_1\rangle$$, where $$T_1$$ is a TM that accepts every input immediately. If $$x\notin A$$ the reduction outputs $$\langle\epsilon, T_2\rangle$$, where $$T_2$$ is a TM that rejects every input immediately. Note that $$T_1,T_2$$ are fixed, i.e. they are hard-coded in the reduction.