1

I have a simple question about the class P:

Is there exist a polynomial time reduction between every two languages A, B in P?

user3699365
  • 111
  • 1

1 Answers1

3

Usually yes, but no in two trivial cases, namely when one of the languages is empty or contains all of the words (over its alphabet). In these trivial cases, nothing else is reducible to such a language. But if $B$ is not trivial in this sense, so that there's at least one word $x$ in $B$ and at least one word $y$ not in $B$, then any language $A$ in $P$ can be reduced to $B$ by the polynomial-time reducing function that sends all words in $A$ to $x$ and sends all words not in $A$ to $y$. (Notice that I didn't need that $B$ is in $P$ for this direction of the reduction.)

Andreas Blass
  • 71,833
  • Yes, I forgot to add that the languages is not trivial. Thank you! – user3699365 Jun 10 '14 at 16:04
  • Thanks for posting this. For the past couple of days I had been thinking about how to answer this question, but I couldn't remember what to do about the case where $B$ was trivial. But you timely reminded me that there is nothing to be done about this case. – MJD Jun 10 '14 at 17:00