I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction.

I've tried to use $L=A_{TM}$ (the accepting problem), but got stuck when for the other language $L'$, I needed the turing machine that accepts it. But how could I summon this machine in polynomal time?

  • 1
    $\begingroup$ Well, for all Turing machines M, the nullary function given by ​ f() = M ​ is computable in polynomial time. ​ ​ ​ (Consider the algorithm "output M".) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Jun 10 '16 at 8:27
  • $\begingroup$ @RickyDemer but I don't know who M is, I only have info regarding L' in the reduction. How can I make the connection? $\endgroup$
    – Mugen
    Jun 10 '16 at 8:29
  • 1
    $\begingroup$ You can look at the definition of $\leqslant_{\hspace{.03 in}p}$ again. ​ (Do you need to "know" the algorithm?) ​ ​ ​ ​ $\endgroup$
    – user12859
    Jun 10 '16 at 8:34
  • $\begingroup$ @RickyDemer well given such L', I know that there exists a machine that accepts it, and if I knew tha machine, I could plot its coding in polynomial time. But where do I get that machine from? I only know it exists, why is that enough? $\endgroup$
    – Mugen
    Jun 10 '16 at 8:36
  • 1
    $\begingroup$ You don't need to get the machine from anywhere. ​ You only need to show that a suitable algorithm exists, not necessary plot such an algorithm. ​ ​ ​ ​ $\endgroup$
    – user12859
    Jun 10 '16 at 8:40

Your Answer

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

Browse other questions tagged or ask your own question.