I'm reading the definition of polynomial time reducible:

Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in L_1\iff f(x)\in L_2$$

For me this means the $L_1$ may be bigger (in cardinality) than $L_2$, but $L_2$ is more difficult since $L_1$ can be solved after reduced to $L_2$?

  • $\begingroup$ How would define the cardinality of an infinite set being larger than another infinite set (both being countable sets)? $\endgroup$
    – dkaeae
    Dec 31, 2018 at 14:53
  • $\begingroup$ You can find examples in which $L_1$ is a strict subset of $L_2$ (and vice versa). $\endgroup$ Dec 31, 2018 at 15:17

1 Answer 1


$L_1$ and $L_2$ are always countably infinite, and thus "equally big".

If any language is finite, then it is "constant time" recognizable.

  • $\begingroup$ I forgot this fact that they're both infinite... Thanks! $\endgroup$
    – Kindred
    Dec 31, 2018 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.