# Are there any RE-complete languages w.r.t. polynomial reduction?

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?

• Well, for all Turing machines M, the nullary function given by ​ f() = M ​ is computable in polynomial time. ​ ​ ​ (Consider the algorithm "output M".) ​ ​ ​ ​ ​ ​ ​ ​ – user12859 Jun 10 '16 at 8:27
• @RickyDemer but I don't know who M is, I only have info regarding L' in the reduction. How can I make the connection? – Mugen Jun 10 '16 at 8:29
• You can look at the definition of $\leqslant_{\hspace{.03 in}p}$ again. ​ (Do you need to "know" the algorithm?) ​ ​ ​ ​ – user12859 Jun 10 '16 at 8:34
• @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? – Mugen Jun 10 '16 at 8:36
• 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. ​ ​ ​ ​ – user12859 Jun 10 '16 at 8:40