$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$.

  • 1
    $\begingroup$ 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=?$ ... $\endgroup$
    – chi
    Jul 11 '17 at 13:28
  • $\begingroup$ I am quite sure that (ii) is wrong. But I have not found a counter-example yet. $\endgroup$
    – Dr Eamton
    Jul 11 '17 at 16:09

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.