$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}\}$?

  • $\begingroup$ What is $L$? What is $A_{TM}$? $\endgroup$ – dkaeae Jul 9 '19 at 14:15
  • $\begingroup$ @dkaeae Please see my edit $\endgroup$ – Dragolis Jul 9 '19 at 14:30
  • $\begingroup$ Which langauge do you think would be a good candidate to be complete in this class? How would you go about proving it? $\endgroup$ – Shaull Jul 9 '19 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jul 9 '19 at 14:38
  • 2
    $\begingroup$ Observe that $L\cup \{A_{TM}\}$ is not a language, it is a class of languages. Try using $A_{TM}$ as a candidate. $\endgroup$ – Shaull Jul 9 '19 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.

Try to prove that this reduction is correct, and that it is indeed in logspace.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.