# polynomial time reducibility, if $A \in \mathbf P$ and $B \in \mathbf N$ $\mathbf P \setminus \{\emptyset,\Sigma^*\}$ and vice versa

$f: \Sigma^* \to \Sigma^*$ is a polynomial time computable function if some poly-time Turing Machine M, on every input w, halts with just $f(w)$ on its tape.

Language $A$ is polynomial time reducible to language $B$, written $A \le_p B$, if there is some polytime computable function $f: \Sigma^* \to \Sigma^*$ such that: $w \in A \iff f(w) \in B$.

I wonder if either $(i)$ or $(ii)$ is correct:

$(i)$ If $A \in \mathbf P$ and $B \in \mathbf N$$\mathbf P \setminus \{\emptyset,\Sigma^*\} , then A is polynomial reducible to B. (ii) If A \in \mathbf N$$\mathbf P \setminus \{\emptyset,\Sigma^*\}$ and $B \in \mathbf P$, then $A$ is not polynomial reducible to $B$.

• For (i), consider taking a string in $B$ and one not in $B$. For (ii), note that $P\subseteq NP$, so we can choose $A=?$ and $B=?$ ...
– chi
Jul 11 '17 at 13:28
• I am quite sure that (ii) is wrong. But I have not found a counter-example yet. Jul 11 '17 at 16:09