Reduction between languages in P

617 Views Asked by At

I have a simple question about the class P:

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

1

There are 1 best solutions below

2
On

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